法算day13

[up主专用，视频内嵌代码贴在这]

最大子数组和

问题描述

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

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

  • 示例 2：
    输入：nums = [1]
    输出：1

  • 示例 3：
    输入：nums = [5,4,-1,7,8]
    输出：23

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

问题分析

使用Kadane算法的核心思想是：遍历数组，计算以每个位置结束的最大子数组和
在每个位置，我们有两个选择：
将当前元素加入前面的子数组
以当前元素开始新的子数组

算法步骤示例（nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]）

  • 初始状态
    1
    2
    currentSum = nums[0] = -2  // 以第0个元素结尾的最大子数组和
    maxSum = nums[0] = -2      // 全局最大子数组和
  • 步骤1：i=1, nums[1]=1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    当前元素: 1
    决策：是将1加入已有子数组[-2]，还是以1开始新的子数组？
    - 选项1：加入已有子数组：currentSum + 1 = -2 + 1 = -1
    - 选项2：开始新子数组：1
    比较：1 > -1，所以选择选项2

    更新：
    currentSum = 1  // 以第1个元素结尾的最大子数组和
    maxSum = max(-2, 1) = 1  // 更新全局最大值

    当前状态：
    以位置1结尾的最大子数组: [1]，和为1
    全局最大子数组: [1]，和为1
  • 步骤2：i=2, nums[2]=-3
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    当前元素: -3
    决策：是将-3加入已有子数组[1]，还是以-3开始新的子数组？
    - 选项1：加入已有子数组：currentSum + (-3) = 1 - 3 = -2
    - 选项2：开始新子数组：-3
    比较：-2 > -3，所以选择选项1

    更新：
    currentSum = -2  // 以第2个元素结尾的最大子数组和
    maxSum = max(1, -2) = 1  // 全局最大值不变

    当前状态：
    以位置2结尾的最大子数组: [1, -3]，和为-2
    全局最大子数组: [1]，和为1
  • 步骤3：i=3, nums[3]=4
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    当前元素: 4
    决策：是将4加入已有子数组[1, -3]，还是以4开始新的子数组？
    - 选项1：加入已有子数组：currentSum + 4 = -2 + 4 = 2
    - 选项2：开始新子数组：4
    比较：4 > 2，所以选择选项2

    更新：
    currentSum = 4  // 以第3个元素结尾的最大子数组和
    maxSum = max(1, 4) = 4  // 更新全局最大值

    当前状态：
    以位置3结尾的最大子数组: [4]，和为4
    全局最大子数组: [4]，和为4
  • 步骤4：i=4, nums[4]=-1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    当前元素: -1
    决策：是将-1加入已有子数组[4]，还是以-1开始新的子数组？
    - 选项1：加入已有子数组：currentSum + (-1) = 4 - 1 = 3
    - 选项2：开始新子数组：-1
    比较：3 > -1，所以选择选项1

    更新：
    currentSum = 3  // 以第4个元素结尾的最大子数组和
    maxSum = max(4, 3) = 4  // 全局最大值不变

    当前状态：
    以位置4结尾的最大子数组: [4, -1]，和为3
    全局最大子数组: [4]，和为4
  • 步骤5：i=5, nums[5]=2
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    当前元素: 2
    决策：是将2加入已有子数组[4, -1]，还是以2开始新的子数组？
    - 选项1：加入已有子数组：currentSum + 2 = 3 + 2 = 5
    - 选项2：开始新子数组：2
    比较：5 > 2，所以选择选项1

    更新：
    currentSum = 5  // 以第5个元素结尾的最大子数组和
    maxSum = max(4, 5) = 5  // 更新全局最大值

    当前状态：
    以位置5结尾的最大子数组: [4, -1, 2]，和为5
    全局最大子数组: [4, -1, 2]，和为5
  • 步骤6：i=6, nums[6]=1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    当前元素: 1
    决策：是将1加入已有子数组[4, -1, 2]，还是以1开始新的子数组？
    - 选项1：加入已有子数组：currentSum + 1 = 5 + 1 = 6
    - 选项2：开始新子数组：1
    比较：6 > 1，所以选择选项1

    更新：
    currentSum = 6  // 以第6个元素结尾的最大子数组和
    maxSum = max(5, 6) = 6  // 更新全局最大值

    当前状态：
    以位置6结尾的最大子数组: [4, -1, 2, 1]，和为6
    全局最大子数组: [4, -1, 2, 1]，和为6
  • 步骤7：i=7, nums[7]=-5
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    当前元素: -5
    决策：是将-5加入已有子数组[4, -1, 2, 1]，还是以-5开始新的子数组？
    - 选项1：加入已有子数组：currentSum + (-5) = 6 - 5 = 1
    - 选项2：开始新子数组：-5
    比较：1 > -5，所以选择选项1

    更新：
    currentSum = 1  // 以第7个元素结尾的最大子数组和
    maxSum = max(6, 1) = 6  // 全局最大值不变

    当前状态：
    以位置7结尾的最大子数组: [4, -1, 2, 1, -5]，和为1
    全局最大子数组: [4, -1, 2, 1]，和为6
  • 步骤8：i=8, nums[8]=4
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    当前元素: 4
    决策：是将4加入已有子数组[4, -1, 2, 1, -5]，还是以4开始新的子数组？
    - 选项1：加入已有子数组：currentSum + 4 = 1 + 4 = 5
    - 选项2：开始新子数组：4
    比较：5 > 4，所以选择选项1

    更新：
    currentSum = 5  // 以第8个元素结尾的最大子数组和
    maxSum = max(6, 5) = 6  // 全局最大值不变

    当前状态：
    以位置8结尾的最大子数组: [4, -1, 2, 1, -5, 4]，和为5
    全局最大子数组: [4, -1, 2, 1]，和为6
  • 最终结果 
    1
    2
    最大子数组和 = 6
    对应的子数组 = [4, -1, 2, 1]

java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
public class MaximumSubarray {
    
    public static int maxSubArray(int[] nums) {
        /**
         * 使用Kadane算法找到最大和的连续子数组
         * 
         * @param nums 整数数组
         * @return 最大子数组的和
         */
        
        // 边界情况：如果数组为空，返回0
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // 初始化当前子数组和和最大子数组和
        int currentSum = nums[0];  // 当前子数组的和
        int maxSum = nums[0];      // 最大子数组的和
        
        // 从数组的第二个元素开始遍历
        for (int i = 1; i < nums.length; i++) {
            // 关键决策：将当前元素加入现有子数组，还是以当前元素开始新的子数组？
            // 如果当前元素值 > 当前子数组和 + 当前元素值，则从当前元素开始新的子数组
            // 否则，将当前元素加入现有子数组
            // 更简单的写法：currentSum = Math.max(nums[i], currentSum + nums[i]);
            // 下面这种写法更容易理解：
            if (currentSum < 0) {
                // 如果当前子数组和为负数，那么它只会减小后面的和
                // 所以放弃之前的子数组，从当前元素开始新的子数组
                currentSum = nums[i];
            } else {
                // 如果当前子数组和为正数或零，继续扩展当前子数组
                currentSum += nums[i];
            }
            
            // 更新最大子数组和
            // 比较当前最大和与新的当前子数组和，取较大值
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
            
            // 上面两步可以合并为一行：
            // currentSum = Math.max(nums[i], currentSum + nums[i]);
            // maxSum = Math.max(maxSum, currentSum);
        }
        
        // 返回最大子数组和
        return maxSum;
    }
    
    // 更简洁的写法（使用Math.max）
    public static int maxSubArrayConcise(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int currentSum = nums[0];
        int maxSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            // 决策：是将当前元素加入已有子数组，还是以当前元素开始新子数组？
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            // 更新最大和
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
    
    // 如果需要同时返回最大子数组的起始和结束位置（扩展版本）
    public static int[] maxSubArrayWithIndices(int[] nums) {
        /**
         * 返回最大子数组的和以及其起始和结束位置
         * 
         * @param nums 整数数组
         * @return 包含[最大和, 起始索引, 结束索引]的数组
         */
        
        if (nums == null || nums.length == 0) {
            return new int[]{0, -1, -1};
        }
        
        int currentSum = nums[0];
        int maxSum = nums[0];
        int currentStart = 0;  // 当前子数组的起始位置
        int maxStart = 0;      // 最大子数组的起始位置
        int maxEnd = 0;        // 最大子数组的结束位置
        
        for (int i = 1; i < nums.length; i++) {
            // 决策：是将当前元素加入已有子数组，还是以当前元素开始新子数组？
            if (currentSum + nums[i] > nums[i]) {
                // 加入已有子数组
                currentSum += nums[i];
            } else {
                // 开始新的子数组
                currentSum = nums[i];
                currentStart = i;
            }
            
            // 更新最大和及其位置
            if (currentSum > maxSum) {
                maxSum = currentSum;
                maxStart = currentStart;
                maxEnd = i;
            }
        }
        
        return new int[]{maxSum, maxStart, maxEnd};
    }
    
    // 测试代码
    public static void main(String[] args) {
        // 示例1
        int[] nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("输入: nums = [-2,1,-3,4,-1,2,1,-5,4]");
        System.out.println("输出: " + maxSubArray(nums1));  // 输出: 6
        System.out.println("简洁版输出: " + maxSubArrayConcise(nums1));  // 输出: 6
        
        // 获取最大子数组的位置
        int[] result1 = maxSubArrayWithIndices(nums1);
        System.out.println("最大和: " + result1[0] + ", 起始位置: " + result1[1] + ", 结束位置: " + result1[2]);
        
        // 示例2
        int[] nums2 = {1};
        System.out.println("\n输入: nums = [1]");
        System.out.println("输出: " + maxSubArray(nums2));  // 输出: 1
        
        // 示例3
        int[] nums3 = {5, 4, -1, 7, 8};
        System.out.println("\n输入: nums = [5,4,-1,7,8]");
        System.out.println("输出: " + maxSubArray(nums3));  // 输出: 23
        
        // 额外测试用例
        int[] nums4 = {-1, -2, -3, -4};
        System.out.println("\n输入: nums = [-1,-2,-3,-4]");
        System.out.println("输出: " + maxSubArray(nums4));  // 输出: -1
        
        int[] nums5 = {-2, -3, 4, -1, -2, 1, 5, -3};
        System.out.println("\n输入: nums = [-2,-3,4,-1,-2,1,5,-3]");
        System.out.println("输出: " + maxSubArray(nums5));  // 输出: 7
    }
}

✅ 说明：

  • 时间复杂度：O(n)，只需要遍历数组一次
  • 空间复杂度：O(1)，只使用了常数个额外变量

python版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def maxSubArray(nums):
    """
    使用Kadane算法计算最大子数组和
    
    参数:
        nums: 整数数组
        
    返回:
        int: 最大子数组和
    """
    # 如果数组为空，返回0
    if not nums:
        return 0
    
    # 初始化当前子数组和为第一个元素
    current_sum = nums[0]
    # 初始化最大子数组和为第一个元素
    max_sum = nums[0]
    
    # 遍历数组，从第二个元素开始
    for i in range(1, len(nums)):
        # 对于当前元素，有两种选择：
        # 1. 将当前元素加入之前的子数组（current_sum + nums[i]）
        # 2. 从当前元素开始新的子数组（nums[i]）
        # 取两者中较大的作为新的当前子数组和
        current_sum = max(nums[i], current_sum + nums[i])
        
        # 更新最大子数组和
        max_sum = max(max_sum, current_sum)
    
    return max_sum

# 测试代码
if __name__ == "__main__":
    # 示例1
    nums1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print(f"输入: nums = {nums1}")
    print(f"输出: {maxSubArray(nums1)}")  # 输出: 6
    print(f"解释: 连续子数组 [4,-1,2,1] 的和最大，为 6")
    
    # 示例2
    nums2 = [1]
    print(f"\n输入: nums = {nums2}")
    print(f"输出: {maxSubArray(nums2)}")  # 输出: 1
    
    # 示例3
    nums3 = [5, 4, -1, 7, 8]
    print(f"\n输入: nums = {nums3}")
    print(f"输出: {maxSubArray(nums3)}")  # 输出: 23
    
    # 额外测试用例
    nums4 = [-1, -2, -3, -4]
    print(f"\n输入: nums = {nums4}")
    print(f"输出: {maxSubArray(nums4)}")  # 输出: -1
    
    nums5 = [1, 2, 3, 4, 5]
    print(f"\n输入: nums = {nums5}")
    print(f"输出: {maxSubArray(nums5)}")  # 输出: 15