Maximum Sub-Array Sum

Finding maximum sum or a subarray in an Array, from brute force approach to most optimze approach

Problem

We are given an array and we have to find maximum sum of a sub array

Sub-Array

For instance we’re given an array e.g.

main.cpp

int arr[] = { 3, -4, 5, 4, -1, 7, -8 };

Now in this array the total number of subarray would be

main.cpp

int n = 5

int totalSub = n * (n + 1) / 2;

// Ans = 15;

To find the subarray of an array’s typical code is

main.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {

    vector<int> vec = { 3, -4, 5, 4, -1, 7, -8 };

    int maxSum = -2147483647;

    for (int i = 0; i < vec.size(); i++) {
        int currSum = 0;

        for (int j = i; j < vec.size(); j++) {
            
            for (int k = i; k < j; k++) {
                cout << vec[k];
            }

            cout << " ";
        }

        cout << "\n";

    }

    cout << "MaxSum: " << maxSum << endl;
    
}

Now when you are doing with finding sub array now one step forward that you have to find the maximum sum of a subarray which you can use this algo to find it

main.cpp

int main() {

    vector<int> vec = { 3, -4, 5, 4, -1, 7, -8 };

    int maxSum = -2147483647;

    for (int i = 0; i < vec.size(); i++) {
        int currSum = 0;

        for (int j = i; j < vec.size(); j++) {
            currSum += vec[j];
            maxSum = max(maxSum, currSum);
        }

    }

    cout << "MaxSum: " << maxSum << endl;
    
}

In this approach we can optimize it using kadan’s Algorithem and it’s code looks like this

main.cpp

int main() {
    vector<int> vec = { 3, -4, 5, 4, -1, 7, -8 };

    int maxSum = 0;
    int currSum = 0;

    for (int i = 0; i < vec.size(); i++) {
        currSum += vec[i];

        maxSum = max(currSum, maxSum);

        if (currSum < 0) {
            currSum = 0;
        }
    }

    cout << "MaxSum: " << maxSum << endl;
}