我将如何着手寻找具有以下条件的数组的最大总和？

Question

在满足以下条件的情况下，我将如何找到数组的最大总和：

求和必须是连续的。
如果存在任何 0，则认为是“中断”
数组中的值不能大于最小值

例子

 1 0 1 0 0 = 1

 2 0 2 1 1 = 3, why? [2 1 1] -> 1 + 1 + 1

 3 1 3 2 2 = 6, why? [3 2 2] -> 2 + 2 + 2

 4 0 0 3 0 = 4

我试着想出一个自下而上的实现方式，跟踪到目前为止的最小值同时跟踪最大总和，但我被卡住了...

Answer 1

有效计算给定元素最小值的范围:

计算每个元素最小的范围为(i,j)，排除i和j。然后将该元素作为该范围内的最小值，总和为 (j-i-1)*element.
取所有这些值中的最大值。
这还应该处理数组中存在的任何零。

如果你仔细想想，这只是另一种询问由直方图.

形成的最大矩形是什么的另一种方式

举个例子：[ 3, 1, 3, 2, 2 ]

对于第一个元素 3 ：它的最小值范围是 (-1,1) 其中 -1 在数组之外并且总和是 3*(1-(-1)-1) = 3

对于第二个元素 1 ：最小值的范围是 (-1,5) 和是 1*(5-(-1)-1) = 5

.....

对于第五个元素 2 ：最小值的范围是 (1, 5) 和是 2*(5-1-1) = 6

对于所有元素，它是：3 5 3 6 6

最大值为6。

如何计算范围？

左边界：

对于任何给定的元素，如果它更大，则向左看，然后取其左边界并继续，直到找到一个小于当前元素的元素。请注意，您不是逐个元素，而是“bounds”。这是重要。
右边界：

你同样向右看，看它是否更大，但继续向右看，直到你找到一个小于当前元素的元素。

Java 中的代码将是：

private static int solve(int[] arr) {
    int n = arr.length;
    int[] leftBound = new int[n];
    int[] rightBound = new int[n];
    leftBound[0] = -1;
    rightBound[n-1] = n;
    for ( int i = 1; i < n; i++ ) {
        int bound = i-1;
        while ( bound >= 0 && arr[bound] >= arr[i] ) {
            bound = leftBound[bound];
        }
        leftBound[i] = bound;
            
    }
    for ( int i = n-2; i >= 0; i-- ) {
        int bound = i+1;
        while ( bound < n && arr[bound] >= arr[i] ) {
            bound = rightBound[bound];
        }
        rightBound[i] = bound;
        
    }
    int res = 0;
    for ( int i = 0; i < n; i++ ) {
        res = Math.max( res, (rightBound[i] - leftBound[i] - 1)*arr[i]);
    }
    return res;
}

我将如何着手寻找具有以下条件的数组的最大总和？

How would I go about finding the maximum sum of an array with the following conditions?

arrays

algorithm

dynamic-programming