题解 | #连续子数组最大和#
连续子数组最大和
https://www.nowcoder.com/practice/1718131e719746e9a56fb29c40cc8f95
描述
给定一个长度为 n\n 的数组，数组中的数为整数。
请你选择一个非空连续子数组，使该子数组所有数之和尽可能大，子数组最小长度为1。求这个最大值。
输入描述：
第一行为一个正整数 n\n ，代表数组的长度。 1\leq n \leq2*10^51≤n≤2∗105
第二行为 n\n 个整数 a_iai，用空格隔开，代表数组中的每一个数。 |a_i| \leq 10^2∣ai∣≤102
输出描述：
连续子数组的最大之和。
示例1
输入：
8 1 -2 3 10 -4 7 2 -5复制
输出：
18复制
说明：
经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18
示例2
输入：
1 2复制
输出：
2复制
示例3
输入：
1 -10复制
输出：
-10
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
while (cin >> n) { // 注意 while 处理多个 case
vector<int> in(n+1, 0);
for (int i = 1; i <= n; i++) {
cin >> in[i];
}
vector<int> dp(n+1, -101);//dp[i]代表以a[i]为结尾的连续子数组的最大和
int sum = 0;
for (int i = 1; i <= n; i++) {
// 对于in[i]来说有两种选择，加入in[i-1]的序列或者另起序列，谁大选谁
dp[i] = max(dp[i-1] + in[i], in[i]);
//cout <<dp[i] << endl;
}
sort(dp.begin(), dp.end());
cout << dp[n] << endl;
return 0;
}
}
// 64 位输出请用 printf("%lld")
投递牛客等公司8个岗位
