题解 | #不相邻最大子序列和#

一个简单的DP，对于每一个数字而言都有两种状态：选或不选，只需要从头至尾遍历，计算选择或不选当前位的结果，选择其中更大的值保存进dp数组，最终输出dp数组的最后一个元素即可。

这里要注意数据可能为负数，当整个数组都只有负数时一个都不选才是最优解，因此需要给dp[0]赋0，dp[1]赋dp[0]（不选arr[0]）和arr[0]（选arr[0]）中的其大数。

function subsequence(n, array) {
  // write code here
  let dp = new Array(n + 1);
  
  dp[0] = 0;
  dp[1] = Math.max(dp[0], array[0]);
  
  for (let i = 2; i <= n; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + array[i - 1]);
  }
//   dp[n]=Math.max(dp[n], dp[n-1]);
  return dp[n];
}
module.exports = {
  subsequence: subsequence,
};