动态规划 - 最大子段和

给定一个数组A[A0,A1,A2,...,An]，求数组中 连续子段之和 的最大值。

(1)最简单的算法：穷举法

计算所有的连续子段之和，得出最大值

/** * { 1, -2, 4, 10, -3, 5, 4, 6, 10, -30 } * max 1  1 4 14 14 16 20 26 36 36 * tmp 1 -1 4 14 11 16 20 26 36 6 * maxSum3的改进版，maxSum3中在最后寻找最大值，可改为在循环过程中只保存M的最大值 */public static int maxSum(int[] data) {int max = data[0], tmp = 0;for (int i = 0; i < data.length; i++) {if (tmp > 0) {tmp += data[i];} else {tmp = data[i];}if (max < tmp) {max = tmp;}}return max;}