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

为了解决这个问题，我们需要找到一个数组中所有子数组的和的最大值。子数组是指数组中连续的一个或多个元素组成的数组。我们需要确保算法的时间复杂度为O(n)，即线性时间。

方法思路

我们可以使用Kadane算法来解决这个问题。Kadane算法的核心思想是遍历数组，同时维护当前的和以及最大和。对于每一个元素，如果将它加入当前的和会比重新开始一个新子数组得到的和更大，那么就加上它，否则就重新开始。这样可以确保我们在每一步都有一个最优的子数组和。

具体步骤如下：

解决代码

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

代码解释

这种方法确保了在O(n)的时间复杂度内解决问题，适用于数组长度较大的情况。