Largest Sum Contiguous Subarray

Table of Contents

Problem Statement

You are given an array of integers. The problem statement asks to find out the largest sum contiguous subarray. This means nothing but to find a subarray (continuous elements) which has the largest sum among all other subarrays in the given array.

Example

arr[] = {1, -3, 4, -2, 5, -6, 2}

[2, 4]

Explanation: The sub-array starting from index 2 to index 4 has the largest sum of 7 within the array. Any other subarray will give a sum smaller than 7.

Largest Sum Contiguous Subarray

arr[] = {1, -3, 4, -1, 4, -2, 5, -6, 2}

[2, 6]

Explanation: The sub-array starting from index 2 to index 6 has the largest sum of 10 within the array.

Algorithm for Largest Sum Contiguous Subarray Problem

1. Set the maxValue to the minimum value an integer can hold (INT_MIN / Integer.MIN_VALUE) and maxPoint to 0.
2. Set start, end, s to 0.
3. Traverse the array starting from i=0 to i<size(length of the array).
  1. Add the maxPoint and arr[i] and update it into the maxPoint.
  2. Check if maxValue is less than maxPoint, then update the following:
    1. maxValue = maxPoint
    2. start=s
    3. end=i
  3. Check if the maxPoint is less than 0, then update
    1. maxPoint=0
    2. s=i+1
4. Print ‘start’ and ‘end’ as an index and the maxValue as the largest sum.

Explanation

We have given an array of integers. We have asked to find out the largest sum contiguous subarray. It can contain negative and positive integers as well. We have to handle all those cases. For this, we are going to traverse the array just for once and hence it has the time of complexity of O(n). We will find the maximum contiguous subarray sum in linear time complexity.

Set up some values, like maxValue to the minimum value an Integer can hold, maxPoint to 0, and start, end, and s to 0. Start traversing the array up to the length n. Add the current array element into the sum maxPoint. Store it into the maxPoint, every time value of i increments in the loop, we do this operation. We have already fixed the value of maxValue to the minimum value of an Integer and check if maxValue is less than maxPoint. If this is true then we are going to update the value of maxValue from maxPoint, start to s. This start variable will set up the value of the starting range of contiguous sub-array and we have an end, which we update with i (loop variable).

We will check now if maxPoint is less than 0, means the addition of array values until now is negative. Then we again update the value of maxPoint to 0 and s to i+1. This s will help us again in setting up the value of starting range and help us find out the largest sum subarray. This maxPoint we will be initialized to zero because we have to find out the largest sum and then we are going to print the value of start and end as a starting and ending indicess of required largest sum sub-array. If we use this approach we can find the largest sum contiguous subarray in a single pass.

Code for Largest Sum Contiguous Subarray Problem

C++ Code

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

// This Function prints the Largest Sum Contiguous Subarray
void getLargestSumContiguousSubarray(int arr[], int size)
{
    // initialising variables with starting values
    int maxValue = INT_MIN;
    int  maxPoint = 0;
    int start =0, end = 0, s=0;

    for (int i=0; i< size; i++ )
    {
        maxPoint += arr[i];

        if (maxValue < maxPoint)
        {
            maxValue = maxPoint;
            start = s;
            end = i;
        }

        if (maxPoint < 0)
        {
            maxPoint = 0;
            s = i + 1;
        }
    }
    cout << "Sub-Array starting from "<< start<< " to "<< end<< " has a largest sum of " <<maxValue;
}
int main()
{
    int arr[] = {1, -3, 4, -2, 5, -6, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    getLargestSumContiguousSubarray(arr, n);
    return 0;
}

Sub-Array starting from 2 to 4 has a largest sum of 7

Java Code

class LargestSumSubArray
{
    // This Function prints Largest Sum Contiguous Subarray
    public static void getLargestSumContiguousSubarray(int arr[], int size)
    {
        // initialising variables with starting values
        int maxValue = Integer.MIN_VALUE;
        int  maxPoint = 0;
        int start =0, end = 0, s=0;

        for (int i=0; i< size; i++ )
        {
            maxPoint += arr[i];

            if (maxValue < maxPoint)
            {
                maxValue = maxPoint;
                start = s;
                end = i;
            }

            if (maxPoint < 0)
            {
                maxPoint = 0;
                s = i + 1;
            }
        }
        System.out.println("Sub-Array starting from "+ start + " to "+ end + " has a largest sum of " + maxValue);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, -3, 4, -2, 5, -6, 2};
        int n = arr.length;
        getLargestSumContiguousSubarray(arr, n);
    }
}

Sub-Array starting from 2 to 4 has a largest sum of 7

Complexity Analysis

Time Complexity

Since we are running a single loop over the input array of size n. Thus algorithm for the largest sum contiguous subarray has linear time complexity. O(n) where “n” is the number of elements in the array.

Space Complexity

We have used a single 1D input array for storing the integers. Thus contributing a linear space complexity to Largest Sum Contiguous Subarray Problem. O(n) where “n” is the number of elements in the array.