Maximum Sub-Array Sum C++

Question

Given an array, I am trying to find the maximum sub-array sum. A sub-array is as follows. For example, I get the following array: [9, -7, 5, 3, 91]. Whilst [9, -7, 5] is a sub-array, [9, 5, 3, 91] is not. My code is below:

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int arraylen, subarraylen, subarraysum, itervar1, itervar2, itervar3, incrementvar;
    cin >> arraylen;
    vector<int> mainarray(arraylen);
    vector<int> sumarray(arraylen * (arraylen-1) + 1);
    for (itervar1 = 0; itervar1 < arraylen; itervar1++) {
        cin >> mainarray[itervar1];
    }
    sumarray[0] = 0;
    for (itervar1 = 0; itervar1 < arraylen; itervar1++) {
        for (itervar2 = arraylen; itervar2 > 0; itervar2--) {
            subarraylen = itervar2-itervar1;
            if (subarraylen < 1) {
                continue;
            }
            vector<int> subarray(subarraylen);
            incrementvar = 0;
            for (itervar3 = itervar1; itervar3 < itervar2; itervar3++) {
                subarray[incrementvar] = mainarray[itervar3];
                incrementvar++;
            }
            subarraysum = 0;
            for (itervar3 = 0; itervar3 < subarraylen; itervar3++) {
                subarraysum += subarray[itervar3];
            }
        }
    }
    return 0;
}

For some reason, it doesn't work; just infinitely loops around. Any help would be appreciated.

Why isn't it a sub array? the numbers have to be consecutive? — Jeff
– Jeff, Commented Oct 25, 2017 at 0:55
I recommend you take some time to read How to debug small programs by Eric Lippert, and learn how to use a debugger to step through your code line by line. — Some programmer dude
– Some programmer dude, Commented Oct 25, 2017 at 0:55

Barmak Shemirani · Accepted Answer · 2017-10-25 04:02:37Z

2

First, here is a routine to list all the sub arrays:

vector<int> vec{ 9, -7, 5, 3, 91 };
int sz = vec.size();
for(int start = 0; start < sz; start++)
{
    for(int end = start; end < sz; end++)
    {
        for(int j = start; j <= end; j++)
        {
            cout << vec[j] << ", ";
        }
        cout << "\n";
    }
}

Now you just have to get the total in loop j, add to a vector sum. You don't need to know the size of sum before hand. Use push_back to add total to sum.

Note, the array itself is included as a sub array, you can exclude that array depending on what the definition is.

answered Oct 25, 2017 at 4:02

Barmak Shemirani

31.8k6 gold badges46 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Arunav MAHESHWARI Over a year ago

When I run this routine, I get an error for your vec{9, -7, 5, 3, 91} assignment line. How can I fix this?

Barmak Shemirani Over a year ago

I used C++ 11 standard to initialize a vector. See here: ideone.com/mNDK0k You have an older compiler, keep using your own method to initialize the vector.

Arunav MAHESHWARI Over a year ago

Thanks for the clarification.

Collectives™ on Stack Overflow

Maximum Sub-Array Sum C++

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related