給一長度為$N$的序列，求最大不連續和(也就是取一段子序列(subsequence)滿足子序列不連續，且和為最大)。
$3\le N\le 10^6, |a_i|\le 10^9$
因為還得紀錄是否連續，所以dp勢必無法只靠一維。
我在想有沒有只需要dp[N][2]的做法，但我想不到QQ，如果有人會還請指教。
我想到的作法是定義:
$dp[N][0]$為前面取過了，但這格不取。
$dp[N][1]$為以$N$為結尾的最大連續子數列(subarray)。
$dp[N][2]$為考慮前$N$項的最大不連續和。
預設都是$-\infty$。
根據定義可以知道
$$dp[N][0]=\max (dp[N-1][0], dp[N-1][1])$$
$$dp[N][1]=\max (dp[N-1][1], 0) + a_N$$
$$dp[N][2]=\max (dp[N-1][0]+a_N, dp[N-1][2]+\max (0, a_N))$$
這樣複雜度就會是好好的$\mathcal{O}(N)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
const ll LINF = 4611686018427387903;
signed main() { EmiliaMyWife
int n;
cin >> n;
vector<int> arr(n + 1);
for(int i = 1; i <= n; i++)
cin >> arr[i];
vector<array<ll, 3>> dp(n + 1, {-LINF, -LINF, -LINF});
for(int i = 1; i <= n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max<ll>(dp[i - 1][1], 0) + arr[i];
dp[i][2] = max(dp[i - 1][0] + arr[i], dp[i - 1][2] + max(0, arr[i]));
}
cout << dp[n][2] << '\n';
}
|