MaxSliceSum

5 -7 3 5 -2 4 -1

这个数组的最大子串是3 5 -2 4

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

思路

O(n) 的解法的关键，是把原来求最优的问题转化为一个具有最优子结构的问题，枚举最大字串的右边界，再在求解其各个子问题解的过程中取最大值。假设以第i个元素结尾的子序列的最大值是maxending，那么以第i+1个元素结尾的子序列的最大值是max(0, maxending+ a[i+1])

代码

int solution(const vector<int> &A) {
    if(A.size() == 0) return 0;
    int max_ending_i = 0;
    int max_slice = A[0];
    for(int i : A){
        max_ending_i = max(i, max_ending_i+i);
        if(max_ending_i > max_slice) max_slice = max_ending_i;
    }
    return max_slice;
}

MaxDoubleSliceSum

A non-empty zero-indexed array A consisting of N integers is given.

A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a?double slice.

The?sum?of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y ? 1] + A[Y + 1] + A[Y + 2] + ... + A[Z ? 1].

For example, array A such that:

?

 A[0] = 3 A[1] = 2 A[2] = 6 A[3] = -1 A[4] = 4 A[5] = 5 A[6] = -1 A[7] = 2

contains the following example double slices:

• double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,
• double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 ? 1 = 16,
• double slice (3, 4, 5), sum is 0.

The goal is to find the maximal sum of any double slice.

Write a function:

int solution(int A[], int N);

that, given a non-empty zero-indexed array A consisting of N integers, returns the maximal sum of any double slice.

For example, given:

?

 A[0] = 3 A[1] = 2 A[2] = 6 A[3] = -1 A[4] = 4 A[5] = 5 A[6] = -1 A[7] = 2

the function should return 17, because no double slice of array A has a sum of greater than 17.

Assume that:

• N is an integer within the range [3..100,000];
• each element of array A is an integer within the range [?10,000..10,000].

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

思路

1. 乍一看这个要比最大子段和高级，似乎要枚举最大字串的右边界i和中间点center，但其实只用枚举右边界i，右边界从i-1变成i之后，中间点只可能是center或者i-1中的一个，中间点为k的时候左边界不变最优，中间点为i-1的时候需要求最优左边界（这就是个内嵌的MaxSliceSum问题）；还有一种情况就是只保留A[i-1]一个元素。整体复杂度仍然是时间 O(N),空间 O(1)。
2. 还有一种思路就是只枚举中间点k，分别算以k-1结尾和k+1开头的最大字段和，然后再把两者拼起来，这种方法整体复杂度是时间 O(N),空间 O(N)。

代码

int solution(vector<int> &A) {
    if(A.size() <= 3) return 0;
    int max_left = 0;//中间点为i-1右边界为i时左段最大值
    int max_ending = 0;//右边界为i时两段最大值
    int center = 1;//中间点
    int max_slice = 0;
    for(int i = 3; i< A.size(); i++){
        max_left = max(max_left+A[i-2], A[i-2]);//MaxSliceSum问题
        max_ending = max(max_ending+A[i-1], A[i-1], max_left);//MaxDoubleSliceSum问题
        if(max_ending == A[i-1]) center = i-2;
        else if(max_ending == max_left) center = i-1;
        if(max_ending > max_slice) max_slice = max_ending;
    }
    return max_slice;
}
inline int max(int a, int b, int c){
   if(b>a) a=b;
   if(c>a) a=c;
   return a;
}