題目要求

P1115題目鏈接

分析

練習DP，勢在必行！

狀態轉移方程：$f[i]=max(f[i?1]+n[i],n[i])$

但 $f[i]$ 未必是答案，這里涉及負數的問題：$n[i]$ 為負數，則 $f[i]<f[i?1]$

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

嗚嗚嗚，這題好像貪心可解 → 薦讀$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);} }

總結

以上是生活随笔為你收集整理的贪心 or 动态规划 求解“最大字段和”问题（洛谷P1115题题解，Java语言描述）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。