求任意两个切片的最大和

Question

我试图解决一个问题，因为我已经有了一个解决方案。问题描述如下：

A non-empty 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:

class Solution { public int solution(int[] A); }

that, given a non-empty 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) (not counting the storage required for input arguments)

解决方案如下：

public static int solution(int[] A) {

        int max = 0;

        int N = A.length;

        int[] A1 = new int[N];
        int[] A2 = new int[N];

        for (int i = 1; i < N - 1; i++) {
            A1[i] = Math.max(A1[i - 1] + A[i], 0);
        }

        for (int i = N - 2; i >= 1; i--) {
            A2[i] = Math.max(A2[i + 1] + A[i], 0);
        }

        for (int i = 1; i < N - 1; i++) {
            max = Math.max(max, A1[i - 1] + A2[i + 1]);
        }

        return max;
    }

我知道在最初的两个循环中做了什么，但是，意图并不清楚。当我接近最后一个for循环时，我的想法变得支离破碎。有人能简单地向我解释一下解决方案吗

Answer 1

我将根据here中的代码进行解释，因为它使用了更清晰的变量名。除此之外，它基本上与您的问题中的代码相同：

class Solution {
    public int solution(int[] A) {        
        int[] maxStartingHere = new int[A.length];
        int[] maxEndingHere = new int[A.length];
        int maxSum = 0, len = A.length;

        for(int i = len - 2; i > 0;  i ) {            
            maxSum = Math.max(0, A[i] + maxSum);
            maxStartingHere[i] = maxSum;
        }
        maxSum = 0;
        for(int i = 1; i < len - 1; ++i ) {            
            maxSum = Math.max(0, A[i] + maxSum);
            maxEndingHere[i] = maxSum;
        }
        int maxDoubleSlice = 0;

        for(int i = 0; i < len - 2; ++i) {
            maxDoubleSlice = Math.max(maxDoubleSlice, maxEndingHere[i] + maxStartingHere[i+2]);
        }

        return maxDoubleSlice;

    }
}

这里的关键是，代码不寻找最大切片，只寻找其总和。数组maxStartingHere在索引i处记录如果从i+1开始合并连续项，将达到的最大总和maxEndingHere反过来也是如此。我们来看一个例子：

i:             0  1  2  3  4
A:             1 -3  2 -1  ...
maxEndingHere: 0  1  0  2  1

请注意：

• i=0：在i中没有剩余的元素，因此总和为0
• i=2：取A[0..1]是次优的，因此0的最大值是通过完全不求和来实现的
• i=4：另一个负元素，但是2 + -1仍然比0好。我们不考虑1 + -3 + 2 + -1，因为我们已经知道2左边的最大值是负数

我希望您看到，这个数组显示了通过选择不同的X可以实现什么，但是X的具体选择并没有被记录下来，只是它的结果。每个i对应于一个Y，而maxEndingHere[i-1]对应于为特定Y最优选择X的结果

所以我们知道，对于一个特定的Y，最佳地选择X和Z的和会产生什么结果。这意味着它只剩下选择最好的Y（或者更准确地说：从最好的Y得到的和）。这就是在第三个循环中发生的事情

重申：

• 当你从一个特定的项目开始时，你能得到的最大值是多少？那是maxStartingHere
• 从任何地方开始，到某个特定项目结束，你能得到的最大值是多少？那是maxEndingHere
• 在某个特定项目结束/开始时，你能得到的最大值是多少？那是maxDoubleSlice