java动态规划求最大字段和

动态规划是一种解决最优化问题的算法思想，特别适用于那些具有重叠子问题和最优子结构的问题，如计算最长公共子序列、背包问题等。在Java中，动态规划通常通过维护一个二维数组或表格来求解最大字段和（Max Subarray Sum），比如著名的“ Kadane’s Algorithm”（卡特兰算法）。

卡特兰算法步骤如下：
1. 初始化两个变量`maxSoFar` 和 `maxEndingHere`，分别表示到当前为止的最大累加和和当前位置的最大累加和。
2. 遍历数组，对于每个元素，做如下操作：
- 如果当前元素加上 `maxEndingHere` 大于0，说明包含当前元素在内的子数组和更大，所以更新 `maxEndingHere` 为当前元素加上 `maxEndingHere` 的值；
- 否则，说明从上一个非负数开始的子数组和更大，将 `maxEndingHere` 重置为当前元素。
- 每次遍历结束后，比较 `maxSoFar` 和 `maxEndingHere`，取较大者作为新的 `maxSoFar`。
3. 当所有元素处理完毕后，`maxSoFar` 就是最长连续正数子数组的和，也就是最大字段和。