Finding the maximum cumulative contiguous array - another version

There are many posts in this forum for finding the largest total subaram. However, a slight variation on this problem is that a subelement must have at least two elements.

For example, for input [-2, 3, 4, -5, 9, -13, 100, -101, 7]

, the code below gives 100. But with the specified limit, it would be 98 with an extra array [3, 4, -5, 9 , -13, 100]

. Can anyone help me to do this? I couldn't get the correct logic for this.

#include<stdio.h>
int maxSubArraySum(int a[], int size)
{
   int max_so_far = 0, max_ending_here = 0;
   int i;
   for(i = 0; i < size; i++)
   {
     max_ending_here = max_ending_here + a[i];
     if(max_ending_here < 0)
        max_ending_here = 0;
     if(max_so_far < max_ending_here)
        max_so_far = max_ending_here;
    }
    return max_so_far;
} 

/*Driver program to test maxSubArraySum*/
int main()
{
   int a[] = {-2, 3, 4, -5, 9, -13, 100, -101, 7};
   int n = sizeof(a)/sizeof(a[0]);
   int max_sum = maxSubArraySum(a, n);
   printf("Maximum contiguous sum is %d\n", max_sum);
   getchar();
   return 0;
}

      

Update 1: Made the change in line with the star change, but I don't understand what I am expecting. This gives 183 instead of 98.

#include<stdio.h>

const int size = 9;

int maxSubArraySum(int a[])
{
    int max_so_far = 0;
    int i;
    int max_ending_here[size];
    int sum_from_here[size];

    max_ending_here[0] = a[0];
    //sum_from_here[0] = a[0] + a[1];

    for (i = 1; i < size; i++)
    {
        max_ending_here[i] = max_ending_here[i-1] + a[i];
        sum_from_here[i] = a[i-1] + a[i];

        if (max_so_far < (max_ending_here[i] + sum_from_here[i]))
            max_so_far = max_ending_here[i] + sum_from_here[i];

    }

    return max_so_far;
}

/*Driver program to test maxSubArraySum*/
int main()
{
    int a[] = { -2, 3, 4, -5, 9, -13, 100, -101, 7 };
    int n = sizeof(a) / sizeof(a[0]);
    int max_sum = maxSubArraySum(a);
    printf("Maximum contiguous sum is %d\n", max_sum);
    getchar();
    return 0;
}

      

+3


source to share


2 answers


An approach:

  • Let be max_ending_here

    an array, whose element max_ending_here[i]

    denotes the maximum sum of subarrays (may be empty) that ends just before the (not included) index i

    . To calculate it, use the same approach as in your function maxSubArraySum

    . The complexity of time O(n)

    , and the complexity of space O(n)

    .

  • Let be sum_from_here

    an array whose element sum_from_here[i]

    denotes the sum of a subar of length-2 starting from the (included) index i

    , which means sum_from_here[i] = a[i] + a[i + 1]

    . The complexity of time O(n)

    , and the complexity of space O(n)

    .

  • Loop over all valid indices and find the maximum value max_ending_here[i] + sum_from_here[i]

    : this value is what you are looking for. The complexity of time O(n)

    , and the complexity of space O(1)

    .

Thus, the overall time complexity O(n)

and space complexity O(n)

.

This approach expands to an arbitrary minimum length - not just 2, and the complexity of time and space doesn't grow.

Your original tool maxSubArraySum

is actually a special case of this approach, in which the minimum subarray length is 0.



Editorial staff:

As per the code you provided in Update 1, I made a few changes and provided the correct version here:

int maxSubArraySum(int a[])
{
    int max_so_far = 0;
    int i;
    int max_ending_here[size];
    int sum_from_here[size];

    max_ending_here[0] = 0;
    for (i = 1; i < size - 1; i++)
    {
        max_ending_here[i] = max_ending_here[i - 1] + a[i - 1];
        if (max_ending_here[i] < 0)
            max_ending_here[i] = 0;
        sum_from_here[i] = a[i] + a[i + 1];

        if (max_so_far < (max_ending_here[i] + sum_from_here[i]))
            max_so_far = max_ending_here[i] + sum_from_here[i];

    }

    return max_so_far;
}

      

Please note that the key max_ending_here[i]

and sum_from_here[i]

do not overlap. Here's an example:

-2   3   4   -5   9   -13   100   -101   7
   | 3   4   -5   9 | -13   100 |
           |              |
           |              |
          this            |
           is             |
    max_ending_here[5]    |
                          |
                         this
                          is
                    sum_from_here[5]

      

+1


source


You can solve this problem using the sliding window algorithm that I have implemented here .

At all points in the algorithm, we support the following

  • Window [lo ... hi].
  • The sum of the current window.
  • A variable called an index that keeps track of an invalid prefix in the current window that will increment the value of the sum. So if we remove the [lo ... index] prefix, the new window becomes [index + 1 ... hi], and the sum will increase as [lo ... index] has a negative sum.
  • The sum of the prefix stored in the prefix variable Sum. It contains the sum for the [lo ... index] interval.
  • Best results found so far.

Initialize

  • window = [0 ... 1]
  • sum = arr [0] + arr 1
  • index = 0
  • prefixSum = arr [0]

Now during each iteration of the while loop



  • Check if a prefix exists in the current window that will increase the value of the sum
  • add the following value to the list to the current interval and change the window and sum variables.
  • Update the variable bestSum.

The following working Java code implements the above explanation.

        int lo = 0;
        int hi = 1;
        int sum = arr[0] + arr[1];
        int index = 0;
        int prefixSum = arr[0];

        int bestSum = sum;
        int bestLo = 0;
        int bestHi = 1;

        while(true){
            // Removes bad prefixes that sum to a negative value. 
            while(true){
                if(hi-index <= 1){
                    break;
                }
                if(prefixSum<0){
                    sum -= prefixSum;
                    lo = index+1;
                    index++;
                    prefixSum = arr[index];
                    break;
                }else{
                    prefixSum += arr[++index];
                }
            }

            // Update the bestSum, bestLo and bestHi variables. 
            if(sum > bestSum){
                bestSum = sum;
                bestLo = lo;
                bestHi = hi;
            }

            if(hi==arr.length-1){
                break;
            }

            // Include arr[hi+1] in the current window. 
            sum += arr[++hi];
        }
        System.out.println("ANS : " + bestSum);
        System.out.println("Interval : " + bestLo + " to " + bestHi);

      

At all points of the algorithm lo + 1 <= hi and at each step of the while loop we increase hi by 1. Also, neither the variable nor the index is ever decremented. Hence the time complexity is linear in the size of the input.

Complexity of time: O(n)


Complexity of space:O(1)

0


source







All Articles