algorithm - 通过对数组值进行加法和减法而不重叠找到可能的最大值

Question

输入

给定一个数组、一个最大值和一个当前值。

目标

对于 array[i] 中的每个 i，array[i] 必须从 current 中添加或减去.我无法准确找出何时应该添加或减去以获得以下输出。

输出

在不高于 maximum 或小于 0 的情况下，current 可能获得的最高值。如果不可能，则返回 -1。

问题

我想出了以下片段，但它不正确。如果我计算每一个可能的答案，然后找到最大的答案，复杂度就会高于 O(n)。我如何知道何时减去或添加？

function calcMax(array, max, current) {
  let output = current;
  for (let i = 0; i < array.length; i++) {
    if (output + array[i] <= max) {
      output += array[i];
    } else {
      output -= array[i];
    }
    return output < 0 ? -1 : output;
  }
}

console.log(calcMax([5, 3, 7], 16, 5))

例子

输入:([15, 2, 9, 10], 20, 8)。 正确输出:-1

输入:([5, 3, 7], 10, 5)。 正确输出:10 (5 - 5 + 3 + 7)

输入:([5, 3, 7], 16, 5)。 正确输出:14 (5 + 5 - 3 + 7)

Answer 1

这个问题在我看来是遍历两条路径——加、减。 如果考虑加、减为 2 条不同的路径，它将形成一个二叉树。例如数组[5, 3, 7] 和max = 16, curr = 5 形成一个二叉树:

                                    5

                              0           10

                                3       7        13

                                 10   0  14   6  

其中左 child 是减法，右 child 是加法。当前值为节点值，要添加的元素为A[i]

观察到二叉树不是满的，因为它受到 [0, max] 的约束。 您会看到它没有小于 0 且大于最大值的节点。

您可以实现基于队列的方法来遍历树并在处理完所有数组元素后找到最后一级的最大值。

伪代码为:

Queue q = new Queue
q.add( current )
int i = 0 //index into array
ans = -1
while ( !q.isEmpty() AND i < A.length )
   int qsize = q.size()
   for ( int j = 0; j < qsize; j++ )
      int currVal = q.poll()
      int addValue = currVal + A[i]
      int subValue = currVal - A[i]
      if ( subValue >= 0 && subValue <= max )
         q.add( subValue );
      if ( addValue >= 0 && addValue <= max )
         q.add( addValue );

   i++

 //now we processed all array elements, now check max value obtained in the last level if any.
 while ( !q.isEmpty ) 
     ans = Math.max( ans, q.poll() )  

 return ans == current ? -1 : ans;