Maximum sum subarray | Kadane’s Algo
Written by
Problem
Given an array of N integers. Find the contiguous sub-array with maximum sum.
Brute Force Approach
We will find the sum of all the subarrays and calculate the max, using two nested for loops.
#include<bits/stdc++.h> using namespace std;
void printLongestSumOfContinuousSubarray(int arr[], int arrSize){ int sumGlobal = 0; for(int i = 0; i < arrSize; i++){ int sum = 0; for(int j = i; j < arrSize; j++){ sum += arr[j]; sumGlobal = max(sumGlobal, sum); } }
cout<<"Max Sum of contanuous subarray: "<<sumGlobal;
}
int main(){ int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}; int arrSize = sizeof(arr)/sizeof(arr[0]); printLongestSumOfContinuousSubarray(arr, arrSize); return 0; }
TC – O(N2)
SC – O(1)
Optimal Approach
In optimized approach, we will use Kadane’s algorithm, We’ll keep a global maximum sum and a local maximum sum.
The local maximum sum at index i is the maximum of A[i] and the sum of A[i] and local maximum sum at index i-1.
#include<bits/stdc++.h> using namespace std;
void printLongestSumOfContinuousSubarray(int arr[], int arrSize){ int localMax = arr[0]; int globalMax = arr[0];
for(int i = 1; i < arrSize; i++){ if(arr[i] > localMax + arr[i]){ localMax = arr[i]; } else { localMax += arr[i]; } if(localMax > globalMax){ globalMax = localMax; } } cout<<"Max Sum of contanuous subarray: "<<globalMax;
}
int main(){ int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}; int arrSize = sizeof(arr)/sizeof(arr[0]); printLongestSumOfContinuousSubarray(arr, arrSize); return 0; }
TC – O(N)
SC – O(1)