1479 最大子序列和 PAT
作者:
NikoNairre
,
2023-11-09 22:59:02
,
所有人可见
,
阅读 95
C++
#include <iostream>
#include <stdlib.h>
using namespace std;
const int N = 10010;
int a[N], dp[N], left_id[N];
/*
a[] is used to record num
dp[i] is the max subsum that ends in a[i](r = i)
left_id[i] is the left idx that ends in a[i](l = left_id[i], r = i)
*/
int max_sq = -0x3f3f3f3f, l = 10010, r = 10010;
//max_sq is the final max subsum, l, r is the final index, actually, l = 0, r = 0 is totally ok
int n;
bool check_negative() //check if all a[] are negative
{
for (int i = 0; i < n; i++ ) {
if (a[i] >= 0) return false;
}
return true;
}
/*
dp rule:
when a[i] is bigger than dp[i - 1] + a[i], that means you don't need the previous part, a single a[i] is better
otherwise, the previous result dp[i - 1] + a[i] will be bigger, so we can include a[i], so cal dp[i] = dp[i - 1] + a[i]
both those two cases need to update left_id[i]
*/
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++ ) cin >> a[i];
if (check_negative()) { //the special case
cout << 0 << " " << a[0] << " " << a[n - 1];
exit(0);
}
dp[0] = a[0], left_id[0] = 0; //dp init
for (int i = 1; i < n; i++ ) {
if (a[i] <= dp[i - 1] + a[i]) { //symbol = can't be omitted because you want to obtain the minimum l in the same max subsum
dp[i] = dp[i - 1] + a[i];
left_id[i] = left_id[i - 1]; //in this case , l isn't change
}
else {
dp[i] = a[i];
left_id[i] = i;
}
}
for (int i = 0; i < n; i++ ) { //scan the dp[] to achieve the final result
if (max_sq < dp[i]) {
max_sq = dp[i];
l = left_id[i], r = i;
}
}
cout << max_sq << " " << a[l] << " " << a[r];
return 0;
}