参考大佬的解法
挑选点赞数最多的不连续编号笔记集合,采用动态规划求解
不连续编号意味着选中nums[i],则不能选择nums[i+1],只能在nums[i+2:]中选择,前面的选择方案直接影响后面的选择,因此采用动态规划求解
dp[i] = x:从 i 开始挑选笔记, 最大点赞数为x
推导过程:从编号i开始挑选时,有以下两种情况:
1. 选择编号i笔记nums[i],意味着nums[i-1]不能选择,此时dp[i]=dp[i-2]+nums[i]
2. 不选择编号i笔记nums[i],此时dp[i]=dp[i-1]
n = int(input()) a = input() nums = [int(i) for i in a.split(" ")] dp = [0 for _ in range(n)] count = [0 for _ in range(n)] dp[0] = nums[0] dp[1] = max(nums[0],nums[1]) count[0] = 1 count[1] = 1 for i in range(2,n): if dp[i-2]+nums[i]>dp[i-1]: # 选择 dp[i]=dp[i-2]+nums[i] count[i] = count[i-2]+1 else: # 不选择 dp[i]=dp[i-1] count[i] = count[i-1] print(dp[n-1],count[n-1])