（最大值之和）

给定整数序列 a0...an-1，求该序列所有非空连续子序列的最大值之和。上述参数满足1<=n<=10^5 和 1<=ai<=10^8

一个序列的非空连续子序列可以用两个下标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=l; i<r-mid; ++i)   __(1)__ ;


		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-1,j=mid,max = 0; i>= l; --i) {


		while (j<r &&  __(2)__ ) ++j;


		max = std::max(max,a[i]);


		ans += __(3)__;


		ans += __(4)__;


	}


	solve(l, mid);


	solve(mid, r);


}





int main() {


	std::cin >> n;


	for (int i=0; i<n; ++i) std::cin >> a[i];


	__(5)__ ;


	std::cout << ans << std::endl;


	return 0;


}

选择题