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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | // // 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