Maximum Sum SubArray with Single Swap

Description The classic Maximum SubArray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

Now we have a new problem based on the classic one - finding the sum of the maximum sum subarray elements after performing a single swap operation. For example, given an array {3, -10, 4, 5}, we can swap 3 and -10 to get a maximum sum subarray {3, 4, 5}, which has the maximum sum 12.

Input The input should be a list of integers with length N, where N should be less than or equal to 1,000,000. The absolute value of each integer of the list should be less than or equal to 1,000.

Output The output should be the sum of the maximum sum subarray elements after performing a single swap operation.

Sample Input 1 2 3 4 5 -1 9 7 8 6

Solutions:

这个想到用DP做的也太牛了！ 只是理解他的思路都用了好一会！

Time: O(n) | Space: O(n)

The first I think about is enumerate the element which will be swapped.

Assume the enumerated element’s index is p, and it swap with element indexed by q.

Here q may be either larger or less than p.

Again we assume q < p.

Then after swapped, the maximum sub-array sum containing array[p] should be sum by two part:

part 1: g[p]-array[p]. g[p]: the maximum sub-array sum start with index p.

part 2: f[p-1]: the maximum sum of sum of a sub-array and a individual element out of the sub-array.

Like this: | …..|||

The indivisual | means the element left outside of the sub-array.

The ||| means sub-array end with array[p-1].

Note that this part can be empty, but the previous part must not.

And f[p-1] is the sum of the two part.

it’s obvious that the indiviual | is used to swap with array[p], which means array[q].

And after swapped, | …..||| —> …..|||| , that is the left part of sub-array containing array[p].

So the problem is how to find the maximum f[p-1].

It’s obvious, f[0] = array[0];

In index i, f[i] may be f[i-1] + array[i], which like this: |….|||| or ….||||

Or f[i] may be max(array[0….i]), which like this: ….|…. or ……| .

So f[i] = max( f[i-1]+array[i], max(array[0…i]));

The answer is max( max(g[0,…n-1]) , max(f[p-1] + g[p]-array[p]) .

The max(g[0…n-1]) means the max sub-array sum without swap.

And in situations p < q, we just reverse the array, and find the answer with the above steps again.

class Solution {
public:
    int getMaxSubarraySum(vector<int> &A) {
        if(A.size()==0)return 0;
        if(A.size()==1)return A[0];

        int ans1=getOneDirectionMax(A);
        reverse(A.begin(),A.end());

        return max(ans1,getOneDirectionMax(A));
    }

    int getOneDirectionMax(vector<int> &A)
    {
        int n=A.size();
        vector<int> f(n),g(n);

        f[0]=A[0];
        int curMax=A[0];
        for(int i=1;i<A.size();i++)
        {
            curMax=max(curMax,A[i]);
            f[i]=max(f[i-1]+A[i],curMax);
        }

        g[n-1]=A[n-1];

        for(int i=n-2;i>=0;i--)
        {
            g[i]=max(g[i+1]+A[i],A[i]);
        }

        int ans=A[0];

        for(int i=1;i<n;i++)
        {
            ans=max(ans,f[i-1]+g[i]-A[i]);
        }

        return ans;
    }
};