分治法求最大字段和java

分治法是一种常见的算法思想，常用于解决一些可以分解为更小规模相似问题的问题，比如求解数组的最大子数组和。在 Java 中，我们可以使用分治法中的 Kadane 算法（也称为动态规划的简化版本）来找到给定数组中的最大字段和。

Kadane 算法的基本步骤如下：
1. 初始化两个变量：`maxSoFar` 和 `currentMax`，分别表示当前已经看到的最大值和从当前位置开始到目前为止的最大连续子数组和。
2. 遍历数组，对于每个元素 `num`：
- 如果 `num` + `currentMax` > `num`，说明以当前元素开头的新子数组和更大，所以更新 `currentMax` = `num + currentMax`。
- 否则，如果 `currentMax` < 0，意味着之前的连续负数导致和变小了，那么从这个元素重新开始计算子数组和，`currentMax` = `num`。
- 同时更新 `maxSoFar`，如果当前的 `currentMax` 比已知的最大和大，则更新它。
3. 遍历结束后，`maxSoFar` 就是整个数组的最大子数组和。

以下是简单的 Java 代码实现：

public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int maxSoFar = nums[0], currentMax = nums[0];
    for (int i = 1; i < nums.length; i++) {
        currentMax = Math.max(nums[i], currentMax + nums[i]);
        maxSoFar = Math.max(maxSoFar, currentMax);
    }
    return maxSoFar;
}