小红书,算法笔试第二题代码
给一个数组 表示点赞的帖子, 要求求不相连的 点赞次数最大,输出 点赞总数 和 贴子数
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)
给一个数组 表示点赞的帖子, 要求求不相连的 点赞次数最大,输出 点赞总数 和 贴子数
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)
全部评论
相关推荐
点赞 评论 收藏
分享
码农索隆:好!开心,给你看看我小区的小猫!
查看图片


点赞 评论 收藏
分享
05-30 00:12
江西服装学院 Java 头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
机械打工仔:这真的不算啥,不能永远活在自己以为的世界里
点赞 评论 收藏
分享