dp1和2应该赋初值
by scp020 @ 2023-10-05 17:11:07
@[scp020](/user/553625) 改了，照 WA 不误。
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define INF -999999999999
int dp[1145140], dp2[1145140];
int arr[1145140];
signed main() {
int n;
cin >> n;
int ans;
dp[0] = dp2[n + 1] = ans = INF;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
for (int i = 1; i <= n; i++) {
dp[i] = max(dp[i - 1] + arr[i], arr[i]);
dp[i] = max(dp[i - 1], dp[i]);
}
for (int i = n; i; i--) {
dp2[i] = max(dp2[i + 1] + arr[i], arr[i]);
dp2[i] = max(dp2[i + 1], dp2[i]);
}
for (int i = 2; i < n; i++) {
ans = max(ans, dp[i - 1] + dp2[i + 1]);
}
cout << ans;
}
```
by 2044_space_elevator @ 2023-10-05 17:15:11
@[2044_space_elevator](/user/824363)
AC code:
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[1145140], dp2[1145140];
int arr[1145140];
signed main() {
int n;
cin >> n;
memset(dp, -127, sizeof(dp));
memset(dp2, -127, sizeof(dp2));
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
for (int i = 1; i <= n; i++) dp[i] = max(dp[i - 1] + arr[i], arr[i]);
for (int i = 1; i <= n; i++) dp[i] = max(dp[i - 1], dp[i]);
for (int i = n; i; i--) dp2[i] = max(dp2[i + 1] + arr[i], arr[i]);
for (int i = n; i; i--) dp2[i] = max(dp2[i + 1], dp2[i]);
int ans = dp[n + 1];
for (int i = 2; i < n; i++) {
ans = max(ans, dp[i - 1] + dp2[i + 1]);
}
cout << ans;
}
```
by robertuu @ 2023-10-05 17:15:38
@[scp020](/user/553625) thx，已悬一关。
@[robertuu](/user/477597) thx，已悬两关。
by 2044_space_elevator @ 2023-10-05 17:16:42
@[2044_space_elevator](/user/824363) 要求的是连续子序列（子串），你那个写法就是正常子序列。连续取最大值需要在全部算完之后
by robertuu @ 2023-10-05 17:16:44
@[2044_space_elevator](/user/824363)
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[1145140], dp2[1145140];
int arr[1145140];
signed main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
dp[1] = arr[1], dp2[n] = arr[n];
for (int i = 2; i <= n; i++) {
dp[i] = max(dp[i - 1] + arr[i], arr[i]);
}
for (int i = 2; i <= n; i++) {
dp[i] = max(dp[i - 1], dp[i]);
}
for (int i = n - 1; i; i--) {
dp2[i] = max(dp2[i + 1] + arr[i], arr[i]);
}
for (int i = n - 1; i; i--) {
dp2[i] = max(dp2[i + 1], dp2[i]);
}
int ans = -0x7fffffffffffffff; // 赋成极小值
for (int i = 2; i < n; i++) {
ans = max(ans, dp[i - 1] + dp2[i + 1]);
}
cout << ans;
}
```
by scp020 @ 2023-10-05 17:21:25
@[scp020](/user/553625) thx
by 2044_space_elevator @ 2023-10-05 17:29:37
@[robertuu](/user/477597) 感谢
by JiuZhE66666 @ 2024-03-25 15:44:05