最大子数组和java

### Java 实现最大子数组和算法 #### 动态规划解法 为了求解给定整数数组中的最大子数组和，可以采用动态规划的方法。这种方法通过维护两个变量`maxSoFar`和`currentMax`来追踪遍历过程中的最大子数组和以及包含当前元素的最大子数组和[^5]。 ```java public class Solution { public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { throw new IllegalArgumentException("Input array is empty or null"); } int currentMax = nums[0]; int maxSoFar = 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; } } ``` 此代码片段展示了如何利用动态规划的思想，在一次线性扫描内完成对最大子数组和的寻找工作。对于每一个位置上的元素，决定它是作为新子序列的起点还是加入到之前的子序列中去取决于它本身与加上前一位置累积值之间的大小比较结果。 #### 分治法解法 另一种解决方案是分治策略，该方法将原问题分解成更小规模相同类型的子问题，并最终合并这些子问题的结果得到整个问题的答案。具体来说就是把数组分成两半分别处理左半部分、右半部分还有跨越中间点的情况下的最优解并从中选取最大的那个作为全局最佳方案[^4]。 ```java class MaxSubArray { private int lSum, rSum, mSum, iSum; public MaxSubArray(int lSum, int rSum, int mSum, int iSum) { this.lSum = lSum; this.rSum = rSum; this.mSum = mSum; this.iSum = iSum; } } public static MaxSubArray pushUp(MaxSubArray l, MaxSubArray r) { int iSum = l.iSum + r.iSum; int lSum = Math.max(l.lSum, l.iSum + r.lSum); int rSum = Math.max(r.rSum, r.iSum + l.rSum); int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum); // 返回结果 return new MaxSubArray(lSum, rSum, mSum, iSum); } ``` 上述代码实现了分治法的核心逻辑——即当我们将一个问题拆分为多个小子问题之后怎样有效地组合它们各自的解答以形成原始问题的最佳答案。这里定义了一个辅助类 `MaxSubArray` 来保存四个重要的属性：左侧最大连续子数组之和(`lSum`)、右侧最大连续子数组之和(`rSum`)、整体最大连续子数组之和(`mSum`) 和 总和 (`iSum`) 。最后调用静态函数 `pushUp()` 完成分割后的重组操作。