给定一个相邻数字之间存在差异的数组，找到原始数组的可能性

Question

给定一个数组，该数组包含一对连续整数与上下限之间的差，找出满足这些条件的可能数组数。

example:

array = [-2, -1, -2, 5]
lowe limit = 3;
upper limit = 10

Ans:
3

explanation:

possible arrays are :
[3,5,6,8,3] => here each element is within limits and difference between adjacent elements is [-2,-1,-2,5]
[4,6,7,9,4] => same as above
[5,7,8,10,5]  => same as above

这是我的程序，但这不是我正在使用的正确方法，因为几天前在hackerrank的几个测试案例中，该程序都失败了：

public static int process(List<Integer> arr, int lower, int higher) {
    int max = Integer.MIN_VALUE;
    int n = lower;
    for (int i = 0; i < arr.size(); i++) {
        int k = arr.get(i);
        int k1 = n - k;
        if (k1 > higher || k1 < lower) {
            return 0;
        }
        n = k1;
        max = Math.max(max, n);
    }

    max = higher - max + 1;

    return max;
}

这项任务的正确方法是什么？

Answer 1

public static void main(String[] args) {
    // TODO Auto-generated method stub
    
    List<Integer> baseArray = new ArrayList<>();
    baseArray.add(-2);
    baseArray.add(-1);
    baseArray.add(-2);
    baseArray.add(5);
    int lower = 3;
    int upper = 10;
    int arrayMatches = 0;
    
    for(int i=lower; i<=upper; i++) {
        boolean match = false;
        int[] array = new int[baseArray.size() + 1];
        int matchCount = 0;
        for(int j = 0; j<=array.length-1; j++) {
            
            if(j == 0) {
                array[j] = i;
                continue;
            }
                
            int matchValue = baseArray.get(j -1);
            
            for(int b=lower; b<=upper;b++) {
                if(array[j-1] - b == matchValue) {
                    matchCount++;
                    array[j]=b;
                }
            }
                
        }
        if(matchCount == baseArray.size()) {
            arrayMatches++;
        }
    }
    System.out.println(arrayMatches);

}

Answer 2

这是Python解决方案：

def countAnalogousArrays(consecutiveDifference , lowerBound , upperBound):

    maxdiff = float('-inf')
    mindiff = float('inf')
    runningsum = 0
    if len(consecutiveDifference) == 0:
        return 0

    if upperBound < lowerBound :
        return 0

    for diff in consecutiveDifference:
        runningsum+=diff
        if runningsum > maxdiff:
            maxdiff = runningsum

        if runningsum < mindiff:
            mindiff = runningsum

    maxvalidupperbound = upperBound + mindiff if upperBound+mindiff < upperBound else upperBound
    minvalidlowerbound = lowerBound + maxdiff if lowerBound + maxdiff > lowerBound else lowerBound

    if maxvalidupperbound >= minvalidlowerbound:
        return maxvalidupperbound - minvalidlowerbound + 1
    else:
        return 0

Answer 3

在我看来你的逻辑是正确的。你能给出一些失败的测试用例吗？

我认为你可以把事情简化一点，因为你选择的变量名称和代码的结构让事情变得更难审查：

int min = 0;
int max = 0;
int current = 0;

for (int val: arr) {
    current += val;
    min = Math.min(min, current);
    max = Math.max(max, current);
}

return Math.max(0, (higher - lower) - (max - min) + 1);

我的代码中的一个不同之处是，我在遍历数组时只计算第一个数字的差值，在计算出答案之前不使用实际范围。这使得算法更易于遵循（IMO）。