QQ扫一扫联系
(最大值之和)给定整数序列
𝑎0,⋯,𝑎𝑛−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105和 1≤ai≤108。一个序列的非空连续子序列可以用两个下标 l 和 r(其中0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar。两个非空连续子序列不同,当且仅当下标不同。
例如,当原序列为 [1,2,1,2] 时,要计算子序列
[1]、[2]、[1]、[2]、[1,2]、[2,1]、[1,2]、[1,2,1]、[2,1,2]、[1,2,1,2] 的最大值之和,答案为 18。注意 [1,1] 和 [2,2] 虽然是原序列的子序列,但不是连续子序列,
所以不应该被计算。另外,注意其中有一些值相同的子序列,但由于他们在原序列中的下标不同,属于不同的非空连续子序列,所以会被分别计算。
解决该问题有许多算法,以下程序使用分治算法,时间复杂度 O(nlogn)。
试补全程序。
#include <iostream> #include <algorithm> #include <vector> const int MAXN = 100000; int n; int a[MAXN]; long long ans; void solve(int l, int r) { if (l + 1 == r) { ans += a[l]; return; } int mid = (l + r) >> 1; std::vector<int> pre(a + mid, a + r); for (int i = 1; i < r - mid; ++i) ①; std::vector<long long> sum(r - mid + 1); for (int i = 0; i < r - mid; ++i) sum[i + 1] = sum[i] + pre[i]; for (int i = mid - l, j = mid, max = 0; i >= l; --i) { while (j < r && ②) ++j; max = std::max(max, a[i]); ans += ③; ans += ④; } solve(l, mid); solve(mid, r); } int main() { std::cin >> n; for (int i = 0; i < n; ++i) std::cin >> a[i]; ⑤; std::cout << ans << std::endl; return 0; }
①处应填()
②处应填()
③处应填()
④处应填()
⑤处应填()
pre[i] = std::max(pre[i - 1], a[i - 1])
pre[i + 1] = std::max(pre[i],pre[i + 1])
pre[i] = std::max(pre[i -1], a[i])
pre[i] = std::max(pre[i], pre[i - 1])
a[j] < max
a[j] < a[i]
pre[j - mid] < max
pre[j - mid] > max
(long long)(j - mid) * max
(long long)(j - mid) * (i - 1) * max
sum[j - mid]
sum[j - mid] * (i - 1)
(long long)(r - j) * max
(long long)(r - j) * (mid - i) * max
sum[r - mid] - sum[j - mid]
(sum[r - mid] - sum[j - mid]) * (mid - i)
solve(0,n)
solve(0,n - 1)
solve(1,n)
solve(1,n - 1)