Hellc

【问题描述】

给定$n$个数 $a_1 , a_2 , ... , a_n$

定义 $$f(i,j) = \sum_{k = i}^{j} a_k$$

求 $f(i,j)$ 的最大值

【题目链接】

CodeVS 3155

【解题思路】

经典问题，最大连续子序列和，有多种解法，是讲解时间复杂度相关的绝好例题(->_->)。

基于动态规划的$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;
}

就是这样啦