题解 | 连续子数组最大和
连续子数组最大和
https://www.nowcoder.com/practice/1718131e719746e9a56fb29c40cc8f95
解题思路
-
使用
算法，维护两个变量：
：记录全局最大和
：记录当前位置结尾的最大和
-
对于每个位置
，有两种选择：
- 将当前数加入前面的子数组（
）
- 从当前数开始新的子数组（
）
- 将当前数加入前面的子数组（
-
每次更新
代码
#include <iostream>
#include <vector>
using namespace std;
int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
int currSum = nums[0];
for(int i = 1; i < nums.size(); i++) {
currSum = max(nums[i], currSum + nums[i]);
maxSum = max(maxSum, currSum);
}
return maxSum;
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for(int i = 0; i < n; i++) {
cin >> nums[i];
}
cout << maxSubArray(nums) << endl;
return 0;
}
import java.util.*;
public class Main {
public static int maxSubArray(int[] nums) {
int maxSum = nums[0];
int currSum = nums[0];
for(int i = 1; i < nums.length; i++) {
currSum = Math.max(nums[i], currSum + nums[i]);
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for(int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
System.out.println(maxSubArray(nums));
}
}
def maxSubArray(nums):
maxSum = nums[0]
currSum = nums[0]
for i in range(1, len(nums)):
currSum = max(nums[i], currSum + nums[i])
maxSum = max(maxSum, currSum)
return maxSum
n = int(input())
nums = list(map(int, input().split()))
print(maxSubArray(nums))
算法及复杂度分析：
- 算法:
算法
- 时间复杂度：
，只需要遍历一次数组
- 空间复杂度：
，只使用了常数额外空间
