360算法笔试0920

四十道选择题，数学，数据结构，代码，cv等等。

code1:

len(nums)=n的数组，数组划分为k段后，求各段权重之和的最大值。

动态规划，感觉很难，很难想到怎么构造dp状态和转移方程

最后还有注意去重

n,k = map(int, input().split())
arr = list(map(int,input().split()))

sum_val = [[0]*n for _ in range(n)]
for l in range(n):
    seen = set()
    total = 0
    for r in range(l,n):
        if arr[r] not in seen:
            total += arr[r]
            seen.add(arr[r])
        sum_val[l][r] = total
dp = [[0]*(k+1) for _ in range(n+1)]
for i in range(1,n+1):
    dp[i][1] = sum_val[0][i-1]

for j in range(2,k+1):
    for i in range(j,n+1):
        best=-10**18
        for m in range(j-1,i):
            current_Val = dp[m][j-1] + sum_val[m][i-1]
            if current_Val > best:
                best = current_Val
        dp[i][j] = best
print(dp[n][k])

code2:

import sys
input_ = sys.stdin.read().split()
idx = 0
T = int(input_[idx])
idx += 1
for _ in range(T):
    n = int(input_[idx])
    idx+=1
    if n==0:
        print(0)
        continue
    h = list(map(int,input_[idx:idx+n]))
    idx += n
    if n==1:
        print(1)
        continue
    
    left = [1]*n
    for i in range(1,n):
        if h[i] > h[i-1]:
            left[i] = left[i-1]+1
        
    right = [1]*n
    for i in range(n-2,-1,-1):
        if h[i]<h[i+1]:
            right[i]=right[i+1]+1
    
    ans = max(left)
    if n >1:
        ans = max(ans,1+right[1])
    if n >1:
        ans = max(ans,1+left[n-1])
    for i in range(1,n-1):
        if h[i-1]<h[i+1] and h[i+1]-h[i-1]>=2:
            ans = max(ans,left[i-1]+1+right[i+1])
        else:
            ans = max(ans,left[i-1]+1,right[i+1]+1)
    print(ans)