时间戳

首页 > 解决方案 > 通过数组值的加法和减法找到可能的最大值而不重叠

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

问题描述

输入

给定一个array，一个maximum值和一个current值。

目标

对于每个iin array[i]，都array[i]必须加上或减去current。我无法确切知道何时应该添加或减去以获得以下output.

输出

电流在不高于maximum或低于 0 的情况下可能获得的最高值。如果不可能，则返回 -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)

标签： algorithmsorting

解决方案

我想出了一个递归解决方案。我认为是 O(n)。

const max = 50;
const current = 20
const array = [20, 30, 4, 14, 16];
let answer = -1;


function calcMax(i, value) {
    
    // Checking the bounds
    if (i === array.length)         {return value}
    if (value > max || value < 0)   {return -1}
    
    
    // With each index compare it with final answer
    let r = 0;
    if (value + array[i] <= max) {
        r = calcMax(i + 1, value + array[i]);
        if (r > answer) {
            answer = r;
        }
    }
    if (value - array[i] >= 0) {
        r = calcMax(i + 1, value - array[i]);
        if (r > answer) {
            answer = r;
        }
    }
    return r;
}


calcMax(0, current);
console.log(answer);

推荐阅读