#P4011. 最大子数组和
-
ID: 2218
Tried: 595
Accepted: 283
Difficulty: 4
最大子数组和
题目内容
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），输出其最大和。
子数组是数组中的一个连续部分。
输入描述
输入共两行。
-
第一行为两个个整数n，代表数组nums的长度。
-
第二行为n个整数nums0,nums1,...,numsn−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<=105
- −104<=nums[i]<=104
最大子数组和（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;
}