Largest Sum Contiguous Subarray

Find the sum of contiguous subarray in a one-dimensional array of numbers which has the largest sum

ALGORITHM 1

TIME COMPLEXITY:  O(N)

SPACE COMPLEXITY: O(1)

We will use DYNAMIC PROGRAMMING approach. It is also known as KADANE’s algorithm.

1. Place two variables max_sum_till_here and overall_max_sum
2. max_sum_till_here stores the maximum sum till the position you are standing.
3. overall_max_sum stores the final result.
  • At each step we check if adding the element to the max_sum_till_here gives us a bigger sum than the present element itself i.e
max_sum_till_here = maximum(cur_element ,cur_element + max_sum_till_here)
This is done to check if we get maximum from single element or some subarray.
  • And we check if overall_max_sum at each step is updated or not
overall_max_sum = maximum(max_sum_till_here , overall_max_sum)

EXAMPLE

In the given example,

max_sum_till_here = -2 and overall_max_sum = -2  //Initial step

At each iteration

  1. max_sum_till_here = max(-3 , -3 + -2) which is -2.
    overall_max_sum = max(-2,-2) which is -2
  2. max_sum_till_here = max(4 , 4 + -2) which is 4.
    overall_max_sum = max(4,-2) which is 4.
  3. max_sum_till_here = max(-1 , -1 + 4) which is 3.
    overall_max_sum = max(3,4) which is 4.
  4. max_sum_till_here = max(-2 , -2 + 3) which is 1.
    overall_max_sum = max(1,4) which is 4.
  5. max_sum_till_here = max(1 , 1 + 1) which is 2.
    overall_max_sum = max(2,4) which is 4.
  6. max_sum_till_here = max(5 , 5 + 2) which is 7.
    overall_max_sum = max(7,4) which is 7.
  7. max_sum_till_here = max(-3 , -3 + 7) which is 4.
    overall_max_sum = max(4,7) which is 7.

Program for Above Logic

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
	int size = sizeof(arr)/sizeof(arr[0]);
	
	int max_sum_till_here = arr[0],overall_max=arr[0];
	for(int i=0;i<size;i++)
	{
		//stores the current max with element comparison
		max_sum_till_here = max(arr[i],arr[i] + max_sum_till_here);

		//stores the overall max
		overall_max = max(max_sum_till_here,overall_max);
	}
	cout<<"Maximum sum of the subcontiguous subarray is  " << overall_max<<endl;
	
	return 0;
}
Try It

ALGORITHM 2

TIME COMPLEXITY: O(N2)
SPACE COMPLEXITY: O(N)

Simply BruteForce by obtaining all the subarray sums and find the maximum among them.

1.    Take an element
2.    Loop from the next element to the end by computing sum at each step and
3.    Compare the sum at each step with the overall maximum

At the end when we compute all the N*(N+1)/2 subarrays we get the maximum.

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
	int size = sizeof(arr)/sizeof(arr[0]);
	
	int max_sum = INT_MIN;
	for(int i=0;i<size;i++)
	{
		int temp_sum = 0;
		//find all the subarrays and their sum
		for(int j=i;j<size;j++)
			{
				temp_sum += arr[j];

				//compare maximum of these subarrays with the overall max obtained till now
				if(temp_sum > max_sum)
					max_sum = temp_sum;
			}
	}
	cout<<"Maximum sum of the subcontiguous subarray is  " << max_sum<<endl;

	return 0;
}
Try It



Next > < Prev
Scroll to Top