从获取数组的左值或右值返回最大值
从获取数组的左值或右值返回最大值
提问于 2019-06-25 21:50:22
{1,2,3,4,1,2,3,4,1}我必须将索引乘以其内部的值。我只能从数组的左边或右边取值。
例如：
如果我只取左边的数字，我会得到1x1 + 2x2 + 3x3 + 4x4+ 1x5 + 2x6 + 3*7 + 4x8 + 1x9 = 109 points.
如果我每次都从右端取数字，我就会得到1x1+4x2+3x3+2x4+1x5+4x6+3x7+2x8+1x9 = 101 points
如果我从左边和右边交替进食(从左边开始)，我会得到1x1+1x2+2x3+4x4+3x5+3x6+4x7+2x8+1x9 = 111 points
然而，正确的解决方案是
1x1+1x2+2x3+3x4+4x5+1x6+2x7+3x8+4x9 = 121 points 我的代码非常难看，但是有没有人能帮助我呢？
public class CandyRoll {
static int total = 0;
static int test (List<Integer> list, int index, int multiplier) {
//Base Case
if (list.size() < 1) { return -1;}
if ((list.get(index) * multiplier) == (list.get(list.size() - 1) * multiplier)){
total = total + list.get(index) * multiplier;
multiplier++;
//list.remove(index);
index++;
test(list, index, multiplier);
} else if ((list.get(index) * multiplier) < (list.get(list.size() - 1) * multiplier)) {
total = total + list.get(index) * multiplier;
multiplier++;
//list.remove(index);
index++;
test(list, index, multiplier);
} else if ((list.get(index) * multiplier) > (list.get(list.size() - 1) * multiplier)) {
total = total + list.get(list.size() - 1) * multiplier;
multiplier++;
//list.remove(list.size() - 1);
index++;
test(list, index, multiplier);
}
//Given example should be 121.
return total;
}
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(1);
int index = 0;
System.out.println(test(list, index, 1));
}
}回答 2
Stack Overflow用户
回答已采纳
发布于 2019-06-26 04:58:59
下面是JavaScript中的一个递归：
function f(A, l=0, r=A.length-1, memo={}){
if (memo.hasOwnProperty([l, r]))
return memo[[l, r]];
const i = A.length - (r - l);
if (l == r)
return memo[[l, r]] = i * A[l];
return memo[[l, r]] = Math.max(
i * A[l] + f(A, l + 1, r, memo),
i * A[r] + f(A, l, r - 1, memo)
);
}
let A = [1,2,3,4,1,2,3,4,1];
console.log(f(A));
Stack Overflow用户
发布于 2019-06-26 00:26:44
如果你做一个小小的心理转变，这个问题就会变得容易得多。与其把它看作是索引乘以当前值，不如把它看作是我取剩下的值之和，然后去掉一个值。所以取{1,2,3,4,1,2,3,4,1}和只取左边的数字，你会得到
(1+2+3+4+1+2+3+4+1) +
( 2+3+4+1+2+3+4+1) +
( 3+4+1+2+3+4+1) +
( 4+1+2+3+4+1) +
( 1+2+3+4+1) +
( 2+3+4+1) +
( 3+4+1) +
( 4+1) +
( 1)而交替将会给你带来：
(1+2+3+4+1+2+3+4+1) +
( 2+3+4+1+2+3+4+1) +
( 2+3+4+1+2+3+4 ) +
( 3+4+1+2+3+4 ) +
( 4+1+2+3 ) +
( 4+1+2 ) +
( 1+2 ) +
( 1 )您的最佳解决方案将变成：
1x1+1x2+2x3+3x4+4x5+1x6+2x7+3x8+4x9
(1+2+3+4+1+2+3+4+1) +
( 2+3+4+1+2+3+4+1) +
( 2+3+4+1+2+3+4 ) +
( 3+4+1+2+3+4 ) +
( 4+1+2+3+4 ) +
( 1+2+3+4 ) +
( 2+3+4 ) +
( 3+4 ) +
( 4 )诸若此类。
很容易验证这是否给出了相同的答案。但是通过这个开关，我们现在递归地解决了原始问题的一个子数组的原始问题。这使得从概念上提出动态编程解决方案变得更加简单。一旦你有了一个概念性的解决方案，代码就可以跟上了。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56755643
复制相关文章
相似问题