构成最大和的数字 [英] Numbers which constitute the Maximum sum
问题描述
我刚刚编写了程序,该程序从数组
中找到最大和,但是我被困在哪里,我有什么办法可以找到哪个数字对最大和有贡献?
I just wrote my program which finds the maximum sum from the array, but I am stuck in is there any way by which I can find which numbers contributed to the max sum?
给出最大和规则:任何相邻元素都不应该贡献
来进行求和。
Rule of Maximum sum is given: No adjacent elements should contribute to sum.
我对数组中最大和的解决方案:
My solution to maximum sum in array:
public class MaximumELementInARray {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
String[] al = reader.nextLine().split(" ");
int[] input = Arrays.stream(al).mapToInt(Integer::parseInt).toArray();
MaximumELementInARray mm = new MaximumELementInARray();
int maxi = mm.maximumm(input);
System.out.println(maxi);
}
public int maximumm(int[] a) {
List<Integer> ex = new ArrayList<>();
List<Integer> inc = new ArrayList<>();
int incl = a[0];
int excl = 0;
int excl_new;
for (int i = 1; i < a.length; i++) {
excl_new = Math.max(incl, excl);
incl = excl + a[i];
excl = excl_new;
}
System.out.println(incl > excl ? inc : ex);
return incl > excl ? incl : excl;
}
}
现在<< c $ c> maximum 函数是否有一个调整项,我可以将构成最大和的所有元素索引放入?
Now in the maximum
function is there a tweak where I can put all the index of elements which constituted to the maximum sum?
输入:
-1 7 8 -5 4 9 -2 3
-1 7 8 -5 4 9 -2 3
输出:
20
**
我要求20是怎么到达的。答案应为 8 + 9 + 3
I require how 20 was arrived at. The answer should say 8+9+3
**
我相信在最大功能下,我们可以放置一个Arraylist并记录哪些元素对总和起作用,但是我无法实现。
I believe that in maximum function we could put an Arraylist and record which which elements are contributing to sum, but I am not able to implement.
我有制成两个Arraylist:
I have made two Arraylist :
List<Integer> ex = new ArrayList<>();
List<Integer> inc = new ArrayList<>();
输入:-1 7 8 -5 4
输出:12
总和由8 + 4
Input: -1 7 8 -5 4 Output: 12 The Sum is made up of 8+4
输入:3 2 1 -1
输出:4
总和由3 + 1
Input: 3 2 1 -1 Output: 4 The sum is made up of 3+1
等...。
推荐答案
您可以遵循此代码。
int toIndex = 3, fromIndex = 0;
List<Integer> result = new ArrayList<>();
while (toIndex < numbers.size()) {
Map<Integer, Integer> map = IntStream
.range(fromIndex, toIndex)
.filter(i->numbers.get(i)>0)
.mapToObj(i -> new AbstractMap.SimpleEntry<>(i, numbers.get(i)))
.collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey,(a,b)->b));
// find max of sublist
int maxOfSub = numbers.subList(fromIndex, toIndex).stream().max(Integer::compareTo).get();
//update indexes
fromIndex = map.getOrDefault(maxOfSub,toIndex-1) + 2;
toIndex += fromIndex;
if (maxOfSub > 0)
result.add(maxOfSub);
}
int lastMax = numbers.subList(fromIndex, numbers.size()).stream().max(Integer::compareTo).get();
if (lastMax > 0)
result.add(lastMax);
System.out.println(result);
System.out.println(result.stream().reduce(0, Integer::sum));
这篇关于构成最大和的数字的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!