Finding a maximum sum contiguous sub array - another version

Question

There are a lot of posts in this forum for finding largest sum contiguous subarray. However, a small variation of this problem is, the sub array should at least have two elements.

For example, for the input [-2, 3, 4, -5, 9, -13, 100, -101, 7] the below code gives 100. But, with the above restriction, it will be 98 with sub array [3, 4, -5, 9 , -13, 100]. Can someone help me do this? I could not get a proper 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 a change according to starrify but I do not get what I'm expecting. It 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;
}

Answer 1

The approach:

1. Let max_ending_here be an array, whose element max_ending_here[i] denotes the maximum sum of subarrays (could be empty) that ends just before (not included) index i. To calculate it, use the same approach as it in your function maxSubArraySum. The time complexity is O(n), and space complexity is O(n).

2. Let sum_from_here be an array, whose element sum_from_here[i] denotes the sum of a length-2 subarray starting from (included) index i, which means sum_from_here[i] = a[i] + a[i + 1]. The time complexity is O(n), and space complexity is O(n).

3. Iterate through all valid indices and find the maximum value of max_ending_here[i] + sum_from_here[i]: that value is what you are looking for. The time complexity is O(n), and space complexity is O(1).

Thus the overall time complexity is O(n) and the space complexity is O(n).

This approach is extendable to arbitrary minimum length -- not only 2, and the time & space complexity do not grow.

Your original implement in maxSubArraySum is actually a special case of this approach above in which the minimum subarray length is 0.

EDITED:

According to the code you provide in update 1, I made a few changes and present a 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;
}

Notice the key is max_ending_here[i] and sum_from_here[i] shall 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]

Answer 2

You can solve this problem by using a sliding-window algorithm which I have implemented here.

At all points during the algorithm we maintain the following

1. A window [lo...hi].
2. The sum of the current window.
3. A variable called index that tracks the bad prefix in the current window removing which will increase the value of the sum. So if we remove the prefix [lo...index] then the new window becomes [index+1 ... hi] and the sum increases as [lo...index] had a negative sum.
4. The sum of the prefix stored in a variable prefixSum. It holds the sum for the interval [lo...index].
5. The bestSum found till now.

Initialize

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

Now during each iteration of the while loop,

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

The following working Java code realizes 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 during the algorithm lo+1<=hi and at each step of the while loop we increment hi by 1. Also neither the variable lo nor index ever decrease. Hence time complexity is linear in the size of the input.

Time complexity : O(n)
Space complexity : O(1)