Why am I getting the last sum as largest sum of subarray?

Question

#include <bits/stdc++.h>
using namespace std;

void printpair(int ar[], int n)
{
    int largestsum = INT_MIN, currentsum = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            currentsum = 0;
            largestsum = INT_MIN;
            for (int k = i; k <= j; k++)
            {
                cout << ar[k] << ",";
                currentsum += ar[k];
            }
            cout << "\n";
        }
        largestsum = max(largestsum, currentsum);
        cout << "the largest sum is " << largestsum << endl;
    }
}

int main()
{
    int n;
    cin >> n;
    int ar[n];
    for (int i = 0; i < n; i++)
        cin >> ar[i];
    printpair(ar, n);
}

When I input:

5
-5 5 6 -7 1

I'm getting output from the first iteration of the outer loop as

-5,
-5,5,
-5,5,6,
-5,5,6,-7,
-5,5,6,-7,1,
the largest sum is 0
...

But it should be 6 as -5 + 5 + 6 = 6 so the largest sum of subarray must be 6, but here it is 0, why!?

Using both ``#include ; using namespace std;`` is a really bad idea. Please don't do it for your own sake. — user438383, Sep 17 '21 at 15:09
`int ar[n];` is illegal in standard C++ (without compiler extensions) since the value of `n` needs to be known at compile time, not run time. Instead prefer `std::vector ar(n);` — Cory Kramer, Sep 17 '21 at 15:11
it is unclear how you can get the reported output with the posted code. As `cout << "the largest sum is " << largestsum << endl;` is inside the loop you print it for each element not only for the last — 463035818_is_not_an_ai, Sep 17 '21 at 15:11
this is the output i get from your code https://godbolt.org/z/ns91zTar5 — 463035818_is_not_an_ai, Sep 17 '21 at 15:12
You reinit `currentsum`, `largestsum` in `j-loop`, so `currentsum ` is only the last sum from `k-loop`. — Jarod42, Sep 17 '21 at 15:12
@463035818_is_not_a_number yes in the first i loop i'm getting 0 as largest sum but it should be 6 as largest sum — Kulbhushan Singh, Sep 17 '21 at 15:19

anastaciu · Accepted Answer · 2021-09-17T17:53:46.157

1

You are not saving the max sum value, you need to do it within the loop:

void printpair(int ar[], int n)
{
    int largestsum = INT_MIN, currentsum = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            currentsum = 0;
            largestsum = INT_MIN;
            for (int k = i; k <= j; k++)
            {
                std::cout << ar[k] << ",";
                currentsum += ar[k];
                largestsum = std::max(largestsum, currentsum);
            }
            std::cout << "\n";
        }
        std::cout << "the largest sum is " << largestsum << std::endl;
    }
}

Note that variable length arrays are not C++ standard, you should not use them, I would also advise you not to use using namespace std; and #include <bits/stdc++.h>;, here are some threads with more on these matters:

Why aren't variable-length arrays part of the C++ standard?

Why is "using namespace std;" considered bad practice?

Why should I not #include <bits/stdc++.h>?

edited Sep 17 '21 at 17:53

answered Sep 17 '21 at 15:43

anastaciu

23,467
7
28
53

hm... isnt `if (largestsum < currentsum) ...` and `largestsum = max(largestsum, currentsum)` somewhat redundant? – 463035818_is_not_an_ai Sep 17 '21 at 15:46
now this line is not much needed: largestsum = max(largestsum, currentsum); – Kulbhushan Singh Sep 17 '21 at 15:48
@463035818_is_not_a_number lol, you have to give me some credit here, I'm looking at this in my phone. – anastaciu Sep 17 '21 at 15:48
now this is printing largest sum for each starting index, but not determining the largest sum of subarray (for any startign index) – 463035818_is_not_an_ai Sep 17 '21 at 15:49
1

better to not spoon feed it all at once – 463035818_is_not_an_ai Sep 17 '21 at 15:51

score 0 · Answer 2 · answered Sep 17 '21 at 15:11

0

You are setting

          largestsum = INT_MIN;

in the inner loop.

answered Sep 17 '21 at 15:11

Sinan Ünür

116,958
15
196
339

yes to reset the largest sum value for next subarray – Kulbhushan Singh Sep 17 '21 at 15:14

Why am I getting the last sum as largest sum of subarray?

2 Answers2