Maximum sum subarray | Kadane’s Algo

Written by

studymite

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&lt;&lt;"Max Sum of contanuous subarray: "&lt;&lt;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 &lt; arrSize; i++){
    	if(arr[i] &gt; localMax + arr[i]){
		localMax = arr[i];
	} else {
		localMax += arr[i];
	}
      
      	if(localMax &gt; globalMax){
		globalMax = localMax;
	}
    }

cout&lt;&lt;"Max Sum of contanuous subarray: "&lt;&lt;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)