本文主要是介绍Partial Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Partial Sum
题目描述
Bobo has a integer sequence a1,a2,…,an of length n. Each time, he selects two ends 0≤l<r≤n and add
into a counter which is zero initially. He repeats the selection for at most m times.
If each end can be selected at most once (either as left or right), find out the maximum sum Bobo may have.
into a counter which is zero initially. He repeats the selection for at most m times. If each end can be selected at most once (either as left or right), find out the maximum sum Bobo may have.
输入
The input contains zero or more test cases and is terminated by end-of-file. For each test case:
The first line contains three integers n, m, C. The second line contains n integers a1,a2,…,an.
2≤n≤105， 1≤2m≤n+1， |ai|,C≤104
The first line contains three integers n, m, C. The second line contains n integers a1,a2,…,an.
2≤n≤105， 1≤2m≤n+1， |ai|,C≤104
The sum of n does not exceed 106.
输出
For each test cases, output an integer which denotes the maximum.
样例输入
4 1 1
-1 2 2 -1
4 2 1
-1 2 2 -1
4 2 2
-1 2 2 -1
4 2 10
-1 2 2 -1
样例输出
3
4
2
0
题目大意：给一个长度为n的数组，寻找l和r（每个l和r只能选择一次），l和r分别代表左右端点计算上面的公式的最大值，m代表最多计算次数（可以是零次），没计算一次sum就加上这次计算的值，找到一个最大的sum。
分析：相当于是计算最大子段和绝对值最大的一段，不止选一次并且选过的端点不能再选。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;int main()
{ll a[100005]={0};ll n,m,c;while(scanf("%lld%lld%lld",&n,&m,&c)!=EOF){a[0]=0;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);a[i]=a[i]+a[i-1];}sort(a,a+n+1);ll ans=0,temp;for(int i=0;i<m;i++){temp=abs(a[n-i]-a[i])-c;if(temp<=0)break;ans+=temp;}printf("%lld\n",ans);}return 0;
}这篇关于Partial Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
![[LeetCode] 404. Sum of Left Leaves](/front/images/it_default2.jpg)
