给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），输出其最大和。
子数组是数组中的一个连续部分。
输入共两行。
第一行为两个个整数n，代表数组nums的长度。
第二行为n个整数nums0,nums1,...,numsn−1，数字之间以空格分隔。
一个整数，表示答案。
输入
9
-2 1 -3 4 -1 2 1 -5 4
输出
6
说明
连续子数组 [4,−1,2,1] 的和最大，为6
输入
1
1
输出
1
输入
5
5 4 -1 7 8
输出
23
本题是典型的 最大子数组和问题，可以使用 Kadane's Algorithm（卡丹算法）高效求解。
maxSum 记录当前找到的最大子数组和。currentSum 维护包含当前元素的最大子数组和。currentSum 为负数，那么加上当前元素只会让和更小，不如从当前元素重新开始，即 currentSum = max(nums[i], currentSum + nums[i])。maxSum = max(maxSum, currentSum) 更新最大子数组和。该算法通过 贪心 的思想，避免了不必要的计算，并且 仅需一次遍历，时间复杂度为 O(n)，适用于大规模数据。
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;
}