最大子数组和（Kadane算法）

题解思路

本题是典型的 最大子数组和问题，可以使用 Kadane's Algorithm（卡丹算法）高效求解。

算法思想

• 使用一个变量 maxSum 记录当前找到的最大子数组和。
• 使用 currentSum 维护包含当前元素的最大子数组和。
• 遍历数组：
  • 如果 currentSum 为负数，那么加上当前元素只会让和更小，不如从当前元素重新开始，即 currentSum = max(nums[i], currentSum + nums[i])。
  • 用 maxSum = max(maxSum, currentSum) 更新最大子数组和。

该算法通过 贪心 的思想，避免了不必要的计算，并且 仅需一次遍历，时间复杂度为 O(n)，适用于大规模数据。

复杂度分析

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

代码实现

Python 代码

class Solution:
    def maxSubArray(self, nums):
        # 初始化最大子数组和为最小值，当前子数组和为0
        maxSum = float('-inf')
        currentSum = 0

        for num in nums:
            # 计算当前最大子数组和
            currentSum = max(num, currentSum + num)
            # 更新全局最大子数组和
            maxSum = max(maxSum, currentSum)

        return maxSum

if __name__ == "__main__":
    # 读取输入
    n = int(input().strip())
    nums = list(map(int, input().split()))
    
    # 计算最大子数组和并输出
    solution = Solution()
    print(solution.maxSubArray(nums))

Java 代码

import java.util.Scanner;

public class Main {
    public class Solution {
        public int maxSubArray(int[] nums) {
            // 初始化最大和和当前子数组和
            int maxSum = Integer.MIN_VALUE;
            int currentSum = 0;

            for (int num : nums) {
                // 计算当前最大子数组和
                currentSum = Math.max(num, currentSum + num);
                // 更新全局最大子数组和
                maxSum = Math.max(maxSum, currentSum);
            }

            return maxSum;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读取数组长度
        int[] nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();  // 读取数组元素
        }
        scanner.close();

        // 计算最大子数组和并输出
        Main main = new Main();
        Solution solution = main.new Solution();
        System.out.println(solution.maxSubArray(nums));
    }
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = INT_MIN;
        int currentSum = 0;

        for (int num : nums) {
            // 计算当前最大子数组和
            currentSum = max(num, currentSum + num);
            // 更新全局最大子数组和
            maxSum = max(maxSum, currentSum);
        }

        return maxSum;
    }
};

int main() {
    int n;
    cin >> n;  // 读取数组长度
    vector<int> nums(n);
    
    for (int i = 0; i < n; i++) {
        cin >> nums[i];  // 读取数组元素
    }

    // 计算最大子数组和并输出
    Solution solution;
    cout << solution.maxSubArray(nums) << endl;

    return 0;
}

Leetcode 13.最大子数组和-原题链接

题目内容

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

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

输入描述

输入共两行。

• 第一行为两个个整数$n$，代表数组$nums$的长度。

• 第二行为$n$个整数$nums_0,nums_1,...,nums_{n-1}$，数字之间以空格分隔。

输出描述

一个整数，表示答案。

样例1

输入

9
-2 1 -3 4 -1 2 1 -5 4	

输出

6

说明

连续子数组 $[4,-1,2,1]$ 的和最大，为$6$

样例2

输入

1
1

输出

1 

样例3

输入

5
5 4 -1 7 8

输出

23

提示

• $1 <= nums.length <= 10^5$
• $-10^4 <= nums[i] <= 10^4$