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

Problem

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

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
//
//  Created by Himanshu on 17/09/21.
//

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

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};

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