第二题是记忆化搜索/区间dp。dp[i][j]表示区间为i到j的最大值。然后就随便搞就行了。