第一题：上n级台阶，一次1步或者2步，不能连续走2步
dp[i][[0] = dp[i-1][0] + dp[i-1][1]
dp[i][1] = dp[i-2][0]
return dp[n][0]+dp[n][1]
第二题：数组下标i从1-n，对每个i，从i向左找到第一个大于A[i]的下标j=L[i]，找不到L[i]=0;从i向右找到第一个大于A[i]的下标k=R[i]，找不到R[i]=0
L[i]*R[i]最大值
单调栈或者二分
从左向右求L[i],二分查找i左边第一个大于Ai的元素j，
从右向求R[i],二分查找i右边第一个大于Ai的元素k
第三题：给定数组A，整数M，求M个A连续组成的最大连续子数组和
sum(A)<0或者dp_end<0 求A的最大连续子数组和即可
dp_end>0,sum(A)>0 dp_end+ (M-2)*sum(A) + start_max(以A首元素开始连续最大和)
第四题：
输出0过20%
第1题10分，后面三题各30分
全部评论
(7) 回帖