【数据结构】最大子数组和

小码同学2023-01-032024-11-21

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

示例

示例1：

1
2
3

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例2：

1 2	输入：nums = [1] 输出：1

示例3：

1 2	输入：nums = [5,4,-1,7,8] 输出：23

实现

方法一：贪心算法

思路：

若当前指针所指元素之前的和小于0，则丢弃当前元素之前的数列。

也就是说，指针指向当前数时，前面的数列如果和小于0，前面的数列就不要了，因为小于0 ，即使加下去也会变得更小，就重新从当前指针开始算最大的数列。

public static int maxSubArray(int[] nums) {
		int sum=0;
        int maxNum =0;
        for (int num:nums){
            if (sum>0){
                sum+=num;
            }else {
                sum=num;
            }
            maxNum=Math.max(sum,maxNum);
        }
        return maxNum;
}

复杂度分析：

时间复杂度：O(N)，只遍历一次数组。
空间复杂度：O(1)，只是用了常数空间。

方法二：动态规划

思路：

若前一个元素大于0，则将其加到当前元素上。

也就是说，如果前面的数时大于0的，那加上后面一个数，肯定是大于后面一个数的，好比5和-2，5+(-2)肯定是大于-2的。

如果前面的数是小于0的，那加起来肯定是小于后一位数的。

public static int maxSubArray(int[] nums) {
        for (int i=1;i<nums.length;i++){
            if (nums[i-1]>0)
                nums[i]+=nums[i-1];
        }
        Arrays.sort(nums);
        return nums[nums.length-1];
}