find the greatest sum of continuous subset, with different conditions

Question

I couldn't find a question relating to this specific problem I am dealing with. So the problem is, to find the continuous subset within an array that has the greatest sum but, the subset's first integer should be greater than its last integer in O(n) time.

For example : 2 4 12 16 3 19 5 20 18 24

The output should be 62, (19 5 20 18). So far I've come up with this algorithm :

  private int biggestSum(int[] arr)
    {
        int startingIndex = 0;
        int endingIndex = 1;
        int sum_so_far = arr[0];
        int sum_biggest = arr[0];
        int count = 0;
        for (int i = 1; i < arr.Length; i++)
        {
            sum_so_far += arr[i];
            count++;
            if (sum_so_far > sum_biggest)
            {
                startingIndex = i - count;
                endingIndex = i;
                sum_biggest = sum_so_far;
            }
            if (sum_so_far < 0)
            {
                sum_so_far = 0;
                count = 0;
            }

        }
        return sum_biggest;
    }

I am able to get the maximum sum of a subset as well as the starting index and ending index of the subset. How can I continue? Or should I take a different approach?

Thanks.

UPDATE : As there are many people that have watched the problem and have not solved it, I would like to know if anyone can prove that this is not doable in O(n) time , although the question mentions clearly that the solution should be in O(n) time.

Answer 1

O(n) solution for non-negative numbers only.

Say the array is a[0], a[1] ... a[n -1], where a[i] >= 0 for 0 <= i < n and the best answer is the subset a[start], a[start + 1], ..., a[end].

We can conclude that a[i] < a[start] for 0 <= i < start, otherwise i -> end would be better solution than start -> end. So the numbers on all possible start points must be ascending.

Similarly, the numbers on all possible end points must be ascending too.

Then we could find the best answer using two iterators. One iterator goes over all possible start points and the other one keeps walking until the last possible end point that satisfies the requirement first integer should be greater than its last integer.

c++ code:

int biggest_sum(const vector<int> &arr)
{
    int n = arr.size();
    // prefix sum
    vector<int> sum(n + 1);
    sum[0] = 0;
    for (int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + arr[i - 1];
    // possible start points
    vector<int> starts;
    starts.push_back(0);
    for (int i = 1; i < n; ++i)
        if (arr[i] > arr[starts.back()])
            starts.push_back(i);
    // possible end points
    vector<int> ends;
    ends.push_back(n - 1);
    for (int i = n - 2; i >= 0; --i)
        if (arr[i] < arr[ends.back()])
            ends.push_back(i);
    reverse(ends.begin(), ends.end());  
    // two iterators walking
    int answer = 0;
    for (int i = 0, j = 0; i < starts.size(); ++i) {
        while (j + 1 < ends.size() && arr[ends[j + 1]] < arr[starts[i]])
            ++j;
        int start = starts[i], end = ends[j];
        if (start < end && arr[start] > arr[end] && sum[end + 1] - sum[start] > answer)
            answer = sum[end + 1] - sum[start];
    }
    return answer;
}