没有找到相似的叫法,网上能搜到的有:
- 最大递增子段和
- 最大上升子段和
不过我更倾向于最大递增子段和
因为其算法与>动态规划版的最大上升子序列<如出一辙
根据名字可以看出,最大上升子序列的意义为:
找出一个数列的递增子列中,和最大的那个子列
采用动态规划的解法:
用 a[i]
来存储数列的第 i
个数
用 dp[i]
来记录到数列的第 i
个数(选取它的情况下)
对于数列中的第 i
个数,显然有 i
种可能:
{% raw %}
1. 子序列上一个是 1
2. 子序列上一个是 2
3. 子序列上一个是 3
4. 子序列上一个是 4
……
i. 从 i
开始
而显然,由于子序列要上升,因此如果 a[j] <= a[i]
这种情况可以直接跳过的
也即 dp[i] = max{ dp[j]+a[i] } (j<i && a[j]<a[i])
由于最后可以从任意地方结束,因此答案不是 dp[n]
而是 dp[]
中最大的值
可以维护一个 Max
变量
数据为 1~n
a[0]
表示起点,初始化为 0
int Max = 0; a[0] = 0; for(int i = 0;i <= n;i++) { dp[i] = 0; for(int j = 0;j < i;j++) if(a[i] > a[j]) dp[i] = max(dp[i],dp[j] + a[i]); Max = max(Max,dp[i]); }