Codility 7.1 Max Double Slice Sum | codesolutiony

Codility 7.1 Max Double Slice Sum | codesolutiony
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.

X.  http://liweithu.me/maximum_slice_problem/
乍一看这个要比最大子段和高级，似乎要枚举最大字串的右边界i和中间点center，但其实只用枚举右边界i，右边界从i-1变成i之后，中间点只可能是center或者i-1中的一个，中间点为k的时候左边界不变最优，中间点为i-1的时候需要求最优左边界（这就是个内嵌的MaxSliceSum问题）；还有一种情况就是只保留A[i-1]一个元素。整体复杂度仍然是时间 O(N),空间 O(1)
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;
}

X.  http://blog.csdn.net/caopengcs/article/details/17491395
还有一种思路就是只枚举中间点k，分别算以k-1结尾和k+1开头的最大字段和，然后再把两者拼起来

1. int solution(vector<int> &A) {  
2.     int n = A.size(), temp = 0;  
3.     vector<int> b;  
4.     b.resize(n);  
5.     for (int i = 1; i < n; ++i) {  
6.         if (temp < 0) {  
7.             temp = 0;  
8.         }  
9.         b[i] = temp;  
10.         temp += A[i];  
11.          
12.     }  
13.     temp = 0;  
14.     int result = 0;  
15.     for (int i = n - 2; i ; --i) {  
16.         if (temp < 0) {  
17.             temp = 0;  
18.         }  
19.         result = max(result, temp + b[i]);  
20.         temp += A[i];  
21.     }  
22.     return result;  
23.           
24.           
25. }

X.

    public int solution(int[] A) {

        int[] fromLeft = new int[A.length];

        int[] fromRight = new int[A.length];

        int max = 0;

        for (int i = 2; i < A.length; i++) {

            fromLeft[i] = Math.max(0, fromLeft[i-1] + A[i-1]);

        }

        for (int i = A.length - 3; i >= 0; i--) {

            fromRight[i] = Math.max(0, fromRight[i+1] + A[i+1]);

        }

        for (int i = 1; i < A.length - 1; i++) {

            max = Math.max(max, fromLeft[i] + fromRight[i]);

        }

        return max;

    }

http://www.cnblogs.com/easonliu/p/4453314.html

 7 int solution(vector<int> &A) {
 8     // write your code in C++11
 9     if (A.size() <= 3) return 0;
10     vector<int> left(A), right(A);
11     int n = A.size();
12     left[0] = left[n-1] = 0;
13     right[0] = right[n-1] = 0;
14     for (int i = 1; i < n - 1; ++i) {
15         left[i] = max(left[i], left[i] + left[i-1]);
16         right[n-1-i] = max(right[n-1-i], right[n-1-i] + right[n-i]);
17     }
18     int res = 0;
19     for (int i = 1; i < n - 1; ++i) {
20         res = max(res, left[i] + right[i] - 2 * A[i]);
21     }
22     return res;
23 }

https://github.com/acprimer/Codility/blob/master/src/Lesson7/MaxDoubleSliceSum.java

	// dp from two directions public int solution(int[] A) {
	int n = A.length;
	int[] dpL = new int[n];
	int[] dpR = new int[n];
	for (int i = 1; i < n - 1; i++) {
	dpL[i] = Math.max(dpL[i - 1] + A[i], 0);
	}
	for (int i = n - 2; i > 0; i--) {
	dpR[i] = Math.max(dpR[i + 1] + A[i], 0);
	}
	int ans = 0;
	for (int i = 1; i < n - 1; i++) {
	ans = Math.max(ans, dpL[i - 1] + dpR[i + 1]);
	}
	return ans;
	}

http://stackoverflow.com/questions/28631437/max-double-slice-sum-codility-o1-space-complexity-fail-performance-test-case

    public int solution(int[] A) {      
        long maxDS = 0;
        long maxDSE = 0;
        long maxS = A[1];

        for(int i=2; i<A.length-1; ++i){                        
            maxDSE = Math.max(maxDSE+A[i], maxS);       
            maxDS = Math.max(maxDS, maxDSE);                                    
            maxS = Math.max(0, Math.max(A[i], maxS + A[i]));     
        }

        return (int)maxDS;
    }

Read full article from Codility 7.1 Max Double Slice Sum | codesolutiony