本文共 1131 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要找到数组中最大的连续子数组的和。连续子数组最少包含一个元素。这个问题可以通过动态规划的方法高效地解决。

方法思路

我们可以使用一个数组 maxSub 来存储从每个索引位置开始的最大连续子数组和。初始化时，最后一个元素的 maxSub 值为它本身，因为它作为单独的子数组只能包含自己。

然后，我们从倒数第二个元素向前遍历：

这样逐步计算出每个位置开始的最大连续子数组和，最终的 result 就是整个数组的最大子数组和。

解决代码

public class Solution {    public int maxSubArray(int[] nums) {        int n = nums.length;        int[] maxSub = new int[n];        maxSub[n-1] = nums[n-1];        int result = maxSub[n-1];                for (int i = n - 2; i >= 0; i--) {            if (nums[i] + maxSub[i + 1] > nums[i]) {                maxSub[i] = nums[i] + maxSub[i + 1];            } else {                maxSub[i] = nums[i];            }            if (maxSub[i] > result) {                result = maxSub[i];            }        }        return result;    }}

代码解释

这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)，高效且适用于较大规模数组。

转载地址：http://vegyk.baihongyu.com/