亚麻OA记录

倒序浏览 · 2022-3-28 18:48:43

记录亚麻OA, 两道题目

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Tongjue_Wang

是弍㈢呜呜吧

匿名用户-FT8EG *2022-3-29 09:02:42* · 2022-3-29 09:02:42

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

yf233

本帖最后由 yf233 于 2022-7-19 14:22 编辑

看了前面大佬的O(n)解法之后按自己理解写了个逻辑更直白的Python解法；

def max_pick(piles):
def _gauss_sum(n, length):
# gauss sum of a consecutively increasing subarray ending at n
return (n-length+1+n)*length//2
increase_stack = []
dp = []
ans = 0
for i, count in enumerate(piles):
# if it follows consecutively increasing subarray pattern, we don't need information about previous items
consecutive = count-1
while increase_stack and piles[increase_stack[-1]] >= consecutive:
increase_stack.pop()
consecutive -= 1
if increase_stack:
# if stack not empty, there is a gap in between, so sum is current consecutive subarray + previous sum
length = i - increase_stack[-1]
curr = _gauss_sum(count, length) + dp[increase_stack[-1]]
else:
# if nothing in stack, then it's a consecutive subarray ends at current count
length = min(i+1, count)
curr = _gauss_sum(count, length)
ans = max(ans, curr)
dp.append(curr)
increase_stack.append(i)
return ans

复制代码

zsp1987

第二题没给sample input 和 out 么？

来自APP · 2022-3-28 22:07:55

zsp1987 发表于 2022-03-28 06:37:25
第二题没给sample input 和 out 么？

有啊，你再看一下example，input是arr, output是那个最大的products

小亩_94b9a9a

蹲个第二题解法，我只能想到o(n2)暴力解

匿名用户-IPO8Y *2022-3-29 06:07:39* · 2022-3-29 06:07:39

請問樓主通過OA了嘛

陈家洛

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

lsh8972

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

chaoqin

wangymdbd

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式