Problem
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 the auxiliary space required is O(1)
Here’s a working example: Maximum Subarray