原题链接：https://www.nowcoder.com/practice/269b4dbd74e540aabd3aa9438208ed8d

描述

给你一个数组，其长度为 n ，在其中选出一个子序列，子序列中任意两个数不能有相邻的下标（子序列可以为空），求该序列的最大子序列和。

本题中子序列指在数组中任意挑选若干个数组成的数组。

思路

一个简单的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,
};

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/147.html
最后修改时间：2022-04-23 14:40:47
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！