亚麻OA记录

第二用维护一个到点递增的栈，思路就是，要找到每个数前面最近的比它小的数，然后分段把每一个区间内递增的加起来

补充内容 (2022-05-31 09:13 +08:00):
本质是个dp,i 依赖于前面一个比他小的j

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

1.     def max_pick(piles):   
   
2.         
   
3.     def _gauss_sum(n, length):
   
4.         # gauss sum of a consecutively increasing subarray ending at n
   
5.         return (n-length+1+n)*length//2
   
6.         
   
7.     increase_stack = []   
   
8.     dp = []
   
9.     ans = 0
   
10.     for i, count in enumerate(piles):   
    
11.         # if it follows consecutively increasing subarray pattern, we don't need information about previous items
    
12.         consecutive = count-1
    
13.         while increase_stack and piles[increase_stack[-1]] >= consecutive:
    
14.             increase_stack.pop()
    
15.             consecutive -= 1
    
16.             
    
17.         if increase_stack:
    
18.             # if stack not empty, there is a gap in between, so sum is current consecutive subarray + previous sum
    
19.             length = i - increase_stack[-1]
    
20.             curr = _gauss_sum(count, length) + dp[increase_stack[-1]]
    
21.         else:
    
22.             # if nothing in stack, then it's a consecutive subarray ends at current count
    
23.             length = min(i+1, count)      
    
24.             curr = _gauss_sum(count, length)
    
25.     ans = max(ans, curr)
    
26.     dp.append(curr)
    
27.     increase_stack.append(i)
    
28.     return ans

复制代码

是弍㈢呜呜吧

Tongjue_Wang 发表于 2022-8-13 21:02
是弍㈢呜呜吧

确实，应该是完全一样的