Kadane's Algorithm

Problem Statement

We are given an array of size n and we need to find the maximum subarray sum.

Note: A subarray is a contiguous section of numbers from the original array

Given:

• $A : [ A_0, A_1 … A_{n-1}] \ (Size = n)$

Brute-Force Approach

The brute-force or naïve approach to this problem is to find the sum of all possible subarrays and then find the maximum among them.

Lets suppose our array is [-1, 2, 4, -3, 5, 2, -5, 2]. The maximum sum of all possible subarrays would be 10. This is from the subarray: [-1, 2, 4, -3, 5, 2, -5, 2]

Code

#include <bits/stdc++.h>
using namespace std;
/**
 * @param A array of elements
*/
int bruteForce(const vector<int>& A)
{
    int n = a.size();
    int maxSum = INT_MIN;
    for(int i = 0; i < n; ++i)
    {
        for(int j = i; j < n; ++j)
        {
            //Current Subarray is: A[i..j]
            int currSum = 0;
            for(int k = i; k <= j; ++k)
                currSum += a[k];
            maxSum = max(maxSum, currSum);
        }
    }
    return maxSum;
}

int main()
{
    vector<int> A = {-1, 2, 4, -3, 5, 2, -5, 2};
    cout << bruteForce(A);

    return 0;
}

Complexity Analysis

• Time complexity: $\boldsymbol{O(n^3)}$ - We are generating all possible subarrays with starting index i and ending index j (A[i..j]) which takes $O(n^2)$ and for each subarray, we are summing all the numbers up which takes $O(n)$ (Hence $ n^2 * n = n^3 $)
• Space complexity: $\boldsymbol{O(1)}$ - We are using no extra space other than the input array.

Note: A[i..j] denotes the subarray starting at index i and ending at index j

Optimized Brute-Force Approach

The brute force approach find the sum of each A[i..j] subarray from the start. However, if we already know the sum for subarray A[i..j-1] we can just find the sum for subarray A[i..j] by adding A[j] to the sum of A[i..j-1]:

Code

#include <bits/stdc++.h>
using namespace std;
/**
 * @param A array of elements
*/
int optimizedBruteForce(const vector<int>& A)
{
    int n = a.size();
    int maxSum = INT_MIN;
    for (int i = 0; i < n; ++i)
    {
        int currSum = 0;
        for (int j = i; j < n; ++j)
        {
            //Current Subarray is: A[i..j]
            currSum += a[j];
            maxSum = max(maxSum, currSum);
        }
    }
    return maxSum;
}

int main()
{
    vector<int> A = {-1, 2, 4, -3, 5, 2, -5, 2};
    cout << bruteForce(A);

    return 0;
}

Complexity Analysis

• Time complexity: $\boldsymbol{O(n^2)}$ - This is because we don’t re-calculate the sum of every subarray.
• Space complexity: $\boldsymbol{O(1)}$ - We are using no extra space other than the input array.

Kadane’s Algorithm

There is an algorithm called kadane’s algorithm which solves this problem in O(n) - Linear time and O(1) - Constant space.

Proof/Working of Kadane’s Algorithm (by Induction)

Let:

• $Sum(i, j)$ denote the sum of the element in the subarry: A[i..j]
• $MaxSum(i)$ denote the maximum sum of all subarrays ending at index i

Our goal is to find the maximum sum of all subarrays which is:

\[\max_{\forall \ i \ \epsilon \ \{0,1...n-1\}}MaxSum(i) = \max(MaxSum(0), MaxSum(1) ... MaxSum(n-1))\]

We know:

\[Sum(i, j) = Sum(i, j-1) + A[j]\]

Using Induction, we can say:

\[MaxSum(i+1) = \max(Sum(0, i) + A[i+1] ... Sum(i, i) + A[i+1], A[i+1])\] \[=\max(Sum(0, i), Sum(1, i) ... Sum(i, i), 0) + A[i+1]\] \[=\max(\max(Sum(0, i), Sum(1, i) ... Sum(i, i)), 0) + A[i+1]\] \[=\max(MaxSum(i), 0) + A[i+1]\] \[=\max(MaxSum(i) + A[i+1], A[i+1])\] \[\therefore MaxSum(i+1)=\max(MaxSum(i) + A[i+1], A[i+1])\]

And the maximum sum of all subarrays will be:

\[\max(MaxSum(0), MaxSum(1) ... MaxSum(n-1))\]

Code

#include <bits/stdc++.h>
using namespace std;
/**
 * @param A array of elements
*/
int kadane(const vector<int>& A)
{
    int n = a.size();
    int sum = 0, best = INT_MIN;
    for (int i = 0; i < n; ++i)
    {
        // MaxSum(i) = max(MaxSum(i-1) + a[i], a[i])
        sum = max(sum + a[i], a[i]); 

        //max(MaxSum(0), MaxSum(1), ... , MaxSum(i))
        best = max(best, sum);
    }
    return best;
}

int main()
{
    vector<int> A = {-1, 2, 4, -3, 5, 2, -5, 2};
    cout << bruteForce(A);

    return 0;
}

Complexity Analysis

• Time complexity: $\boldsymbol{O(n)}$ - We are going through the array once
• Space complexity: $\boldsymbol{O(1)}$ - We are using no extra space other than the input array.