【问题描述】
给定$n$个数 $a_1 , a_2 , ... , a_n$
定义 $$f(i,j) = \sum_{k = i}^{j} a_k$$
求 $f(i,j)$ 的最大值
【题目链接】
【解题思路】
经典问题,最大连续子序列和,有多种解法,是讲解时间复杂度相关的绝好例题(->_->)。
基于动态规划的$O(n)$做法: 设$f_i$表示以$i$为终点的最大连续子序列和,则: $$f_i = max(f_{i - 1} + a_i,\ a_i) \\ \ \ = max(f_{i - 1}, 0) +a_i$$ 答案为所有$f_i$最大值。
可以利用滚动数组优化空间复杂度到$O(1)$。
【AC代码】
#include <cstdio>
#include <algorithm>
int main(){
int n;
scanf("%d", &n);
int sum = 0, ans = 0;
for(int i = 0; i < n; i++){
int x;
scanf("%d", &x);
sum = std::max(sum, 0) + x;
ans = std::max(ans, sum);
}
printf("%d\n", ans);
return 0;
}
就是这样啦