小红书:秋招算法笔试 第二题
给一个数组 表示点赞的帖子, 要求求不相连的 点赞次数最大,输出 点赞总数 和 贴子数
if __name__ == "__main__": n = int(input()) zan = [int(x) for x in input().strip().split(' ')] dp = [[0 for _ in range(2)] for _ in range(n)] dp[0][0] = 0 dp[0][1] = zan[0] state_0 = [] state_1 = [zan[0]] for i in range(1, n): if dp[i-1][1] > dp[i-1][0]: dp[i][0] = dp[i-1][1] tem = state_0 state_0 = state_1 dp[i][1] = dp[i-1][0] + zan[i] state_1 = tem state_1.append(zan[i]) else: dp[i][0] = dp[i-1][0] dp[i][1] = dp[i-1][0]+zan[i] state_1 = state_0[:] state_1.append(zan[i]) if dp[n-1][0] > dp[n-1][1]: tol = dp[n-1][0] res = len(state_0) else: tol = dp[n-1][1] res = len(state_1) # print(state_0) # print(state_1) print(tol, res)