algorithm - 最大和序列使得没有两个元素是相邻的

Question

我的最大和实现如下，但我需要给出最大和的序列google，stackoverflow但没有输出序列。

public int maxSum(int arr[]) {
     int excl = 0;
     int incl = arr[0];
     for (int i = 1; i < arr.length; i++) {
       int temp = incl;
       incl = Math.max(excl + arr[i], incl);
       excl = temp;
     }
     return incl;
}

所以 3 2 7 10 应该返回 (3 and 10) 或 3 2 5 10 7 应该返回 (3, 5 and 7) 或者 {5, 5, 10, 100, 10, 5} 将返回 (5, 100 and 5)或 {1, 20, 3} 将返回 20 我完全想要这个问题的解决方案，但我需要的返回值是包含在最大总和而不是最大总和值中的元素序列

标签： algorithmdynamic-programming

Answer 1

看起来类似于最长增加片段问题（自上而下的方法）。您可以返回它的总和，而不是序列的长度。此外，不要跳过一个，而是跳过两个以避免相邻的元素。