Find the Maximum Subarray and its Sum [Kadane’s Algorithm]

Find the maximum subarray and its sum is a problem of finding contiguous subarray with largest sum in an array of integers.

Kadane’s Algorithm (A[]) (Pseudocode)

1. maxSum = INT_MIN, curMax = 0, maxL = maxR = 0, l = r = 0;
2. for i = 0 to n-1
3.   do currMax += A[i]
5.   if currMax > maxSum
6.     maxSum = currMax
7.     r = i; maxL = l, maxR = r;
8.   if currMax < 0
9.     currMax = 0;
10.    l = i+1; r = i+1;

Code Implementation

//
//  main.cpp
//  Kadane's Algorithm
//
//  Created by Himanshu on 17/09/21.
//

#include <iostream>
using namespace std;
const int N = 8;

void KadanesAlgorithm (int A[]) {
    int maxSum = INT8_MIN, maxL = 0, maxR = 0, currMax = 0, l = 0, r = 0;
    
    for (int i=0; i<N; i++) {
        currMax += A[i];
        if (currMax > maxSum) {
            maxSum =currMax;
            r = i;
            maxL = l;
            maxR = r;
        }
        if (currMax < 0) {
            currMax = 0;
            l = i+1;
            r = i+1;
        }
    }
    
    cout<<"Max contiguous subarray is A["<<maxL<<", "<<maxR<<"] with sum: "<<maxSum<<endl;
    
}
 
int main() {
    int A[N] = {5, 3, -4, 6, -9, 8, 11, -20};
    KadanesAlgorithm(A);
}

Output:

Max contiguous subarray is A[0, 6] with sum: 20

Time complexity of the above solution is O(n) and auxiliary space required is O(1)

Here’s a working example:

https://ideone.com/INZJQh

Leave a Reply

Your email address will not be published.