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)

Report Error/ Suggestion

Related Posts:



CopyRight © 2020

CopyRight © 2020