简答题 偏难
#22267

(最大值之和)给定整数序列a 0 ,… a n-1 ,求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤10 5 和1≤a;≤10 8 。 一个序列的…

(最大值之和)给定整数序列a0,… an-1,求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤105和1≤a;≤108。

一个序列的非空连续子序列可以用两个下标l和r(其中0≤l≤r<n)表示,对应的序列为alal+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]和[22]虽然是原序列的子序列,但不是连续子序列,所以不应该被计算。另外,注意其中有一些值相同的子序列,但由于他们在原序列中的下标不同,属于不同的非空连续子序列,所以会被分别计算。解决该问题有许多算法,以下程序使用分治算法,时间复杂度0(nlogn)。

试补全程序。

未登录也能判分,登录后才会记录
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。