TutorialStudyMite
Maximum sum subarray | Kadane’s Algo
Sstudymite1 min read
Beginner friendly
Track completion, mastery, and revision.
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);
}
}
}
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];
}
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)
Finished reading?