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]