【牛客】不相邻最大子序列和
浏览 50 | 评论 0 | 字数 773
TTQ
2022年04月23日
  • 原题链接:https://www.nowcoder.com/practice/269b4dbd74e540aabd3aa9438208ed8d

    描述

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

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

    思路

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

    这里要注意数据可能为负数,当整个数组都只有负数时一个都不选才是最优解,因此需要给dp[0]0dp[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 授权协议,转载请注明来源,谢谢!
    评论
    与本文无关评论请发留言板。请不要水评论,谢谢。
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论