贪心 or 动态规划 求解“最大字段和”问题（洛谷P1115题题解，Java语言描述）

题目要求

P1115题目链接

分析

练习DP，势在必行！

状态转移方程：$f[i]=max(f[i-1]+n[i], n[i])$f[i]=max(f[i−1]+n[i],n[i])

但 $f[i]$f[i] 未必是答案，这里涉及负数的问题：$n[i]$n[i] 为负数，则 $f[i] < f[i-1]$f[i]<f[i−1]

所以还需要比较 $f[i]$f[i] 和 $max$max 的大小啦……

呜呜呜，这题好像贪心可解 → 荐读$dalao$dalao博文，这做法我也没细研究，大家感兴趣就自行食用吧！

AC代码（Java语言描述）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(reader.readLine()), max;
        if (num == 0) {
            reader.close();
            System.out.println(0);
            return;
        }
        String[] nums = reader.readLine().split("\\s+");
        reader.close();
        int[] result = new int[num+1];
        result[1] = max = Integer.parseInt(nums[0]);
        for (int i = 2; i <= num; i++) {
            int tempNum = Integer.parseInt(nums[i-1]);
            result[i] = Math.max(result[i-1]+tempNum, tempNum);
            max = Math.max(result[i], max);
        }
        System.out.println(max);
    }
}