HDU 1422 - Chong Wen Shi Jie Bei
Problem : There are N numbers in a circle. Find a maximum length segment on the circle, s.t. start at one of the endpoint and walk in clockwise, until reach another endpoint, the sum of walked number is always non-negative.
Solution :
1) Transform the circle to the sequence with length 2N (choose any number to start is OK), since all the segment with length no more than n has corresponding segment on the circle. The answer of the circle format is equivalent with the answer of the sequence. (If the answer on sequence larger than n, then the answer is n).
2) Denote f[i] the length of longest valid segment which is ended at the i-th number of the sequence, v[i] is the sum of that segment. Then v[i]=v[i-1]+a[i]>=0?v[i-1]+a[i]:0; f[i]=v[i-1]+a[i]>=0?f[i-1]+1:0.
proof: Denote head[i] to be the head of the longest valid segment which is ended at the i-th number of sequence. By definition, head[i] cannot be smaller than head[i-1], otherwise head[i-1] can be move to head[i] and the segment is still valid. If v[i-1]+a[i]>=0, it is valid to append a[i] to a[head[i]..i-1] to get a longer valid sequence. If v[i-1]+a[i]<0, then there's no valid segment end at i. Since sum(a[head[i-1]..j]) (head[i-1]<=j<=i-1) always >= 0, sum(a[j+1..i])=sum(a[head[i-1]..i])-sum(a[head[i-1]..j])<=sum(a[head[i-1]..i])<0. Thus start at j=[head[i-1], i], the segment are all invalid. It also impossiblely valid to start before head[i-1], which is mentioned before. Thus the theory always hold.