2013
12-23

# Max Partial Value I

HenryFour has a number of stones which have different values from -4444 to 4444. He puts N stones in a line and wants to find the max partial value of these N stones.

Assume the values of the N stones in line are: v1, v2, v3, v4, …, vN. The partial vaule of stones from Lth stone to Rth stone (1 ≤ L ≤ R ≤ N) is the sum of all the stones between them. i.e. PartialV(L, R) = v[L] + v[L+1] + …. + v[R] (1 ≤ L ≤ R ≤ N)

Since the number of stones (N) is very very large, it is quite difficult for HenryFour to find the max partial value. So could you develop a programme to find out the answer for him?

There are several test cases in the input data. The first line contains a positive integer T (1 ≤ T ≤ 14), specifying the number ot test cases. Then there are T lines. Each of these T lines contains a positive number N followed by N integers which indicate the values of the N stones in line.
1 ≤ N ≤ 1,000,000
-4444 ≤ v[i] ≤ 4444

Your program is to write to standard output. For each test case, print one line with three numbers seperated by one blank: P L R. P is the max partial value of the N stones in line. L and R indicate the position of the partial stones. If there are several Ls and Rs that have the same value PartialV(Li, Ri) = P, please output the minimum pair. For pair (Li, Ri) and (Lj, Rj), we define (Li, Ri) < (Lj, Rj) if and only if: Li < Lj or (Li == Lj and Ri < Rj)

3
4 32 -39 -30 -28
8 1 2 3 -10 1 -1 5 1
10 14 -12 -8 -13 3 5 42 -24 -32 -12

32 1 1
6 1 3
50 5 7

Hint Huge input and output,scanf and printf are recommended. 

#include<stdio.h>
#define inf 0x7fffffff
struct node
{
int l;
int r;
__int64 w;
}p[1000000];
__int64 a[1000000];
int main()
{
int t,i,k,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%I64d",&a[i]);
p[i].w=a[i];
p[i].l=p[i].r=i;
}
p[0].w=0;
p[0].l=1;
__int64 max=-inf;
for(i=1;i<=n;i++)
{
if(p[i].w<=p[i-1].w+a[i])
{
p[i].w=p[i-1].w+a[i];
p[i].l=p[i-1].l;

}
if(p[i].w>max)
{
max=p[i].w;
k=i;
}
}
printf("%I64d %d %d\n",max,p[k].l,p[k].r);

}
}

1. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}

2. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.