Size of The Subarray With Maximum Sum

Problem Statement

You are given an array of integers. The given array can contain both positive and negative numbers. Find out the size of the subarray with maximum sum.

Example

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

4

Explanation: 2 -1 + 4 + 3 = 8 is maximum sum of length 4

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

2

Explanation: 1 + 2 = 3 is maximum sum of length 2

Algorithm

1. Set the maxVal to the minimum value of an integer and maxPoint to 0, start, end, and s to 0.
2. Starting from i=0 to i<size(length of the array).
  1. Sum up the value of maximumPoint and arr[i] and store into the maximumPoint.
  2. Check if maxVal is less than maxPoint, then update the following:
    maxVal = maxPoint
    start=s
    nd=i
  3. Check if the maximumPoint is less than 0, then update
    maximumPoint=0
    s=i+1
3. Return the value (end – start + 1).

Explanation for calculating size of the subarray with maximum sum

Given an array of integers numbers. Our task is to find the length of the subarray which has the maximum sum. It can contain negative and positive integer numbers too. We are going to traverse the exhibit only for once and subsequently, it has the time complexity of O(n). Locate the biggest sub-value total in linear time complexity.

Set up certain values of the variable, like maxValue to the minimum value of an Integer, maxPoint to 0, and start, end, and s to 0. Start traversing the array up to the length n. Include the current array element into the total maxPoint and store it into the maxPoint, each time when the value of i increases in the loop.

Set up the value of maxValue to the minimum value of an Integer and check on the off chance that maxValue is not greater than maxPoint, in the event that it is valid, at that point we are going to update the value of maxValue from maxPoint, start to s, this beginning variable will set up the value of starting range of contiguous subarray and we have end, which we are going to update it with i.

We will check now if maxPoint is less than 0, this implies the sum of the sub-array being negative, at that point we are going to 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 assist us with finding out the biggest sum subarray. This maxPoint we will initialize as zero since we need to find the biggest sum and afterward we are going to return the value as end-start+1. This return value will be the largest sub-array length of the maximum sum.

Implementation in C++ for finding the size of the subarray with maximum sum

#include<bits/stdc++.h>

using namespace std;

int getSizeMaxSum (int arr[], int size)
{
    int maxVal = INT_MIN, maximumPoint = 0,
        start =0, end = 0, s=0;

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

        if (maxVal < maximumPoint)
        {
            maxVal = maximumPoint;
            start = s;
            end = i;
        }

        if (maximumPoint < 0)
        {
            maximumPoint = 0;
            s = i + 1;
        }
    }

    return (end - start + 1);
}
int main()
{
    int arr[] = {1, -2, 1, 1, -2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getSizeMaxSum(arr, n);
    return 0;
}

2

Implementation in Java for size of the subarray with maximum sum

class SubArraySizeMaximumSum
{

    public static int getSizeMaxSum (int arr[], int size)
    {
        int maxVal = Integer.MIN_VALUE,
            maximumPoint = 0,start = 0,
            end = 0, s = 0;

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

            if (maxVal < maximumPoint)
            {
                maxVal = maximumPoint;
                start = s;
                end = i;
            }

            if (maximumPoint < 0)
            {
                maximumPoint = 0;
                s = i + 1;
            }
        }
        return (end - start + 1);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, -2, 1, 1, -2, 1};
        int n = arr.length;
        System.out.println(getSizeMaxSum(arr, n));
    }
}

2

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. We have only used a single loop just for traversing array once, thus making it a linear time complexity solution.

Space Complexity

O(n) where “n” is the number of elements in the array. Since we used a single array of size n, we have linear space complexity as well.