andy6804tw
8/6/2016 - 9:08 AM

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1625&mosmsg=Submission+received+wi

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1625&mosmsg=Submission+received+with+ID+17796056

這題使用貪婪法,一個有序的數列中,累積總和遇到負數歸零,時間複雜度O(N)

Q10684 : The jackpot.java
content_copyfile_download
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		while (scn.hasNext()) {
			int n=scn.nextInt(),max=0,tot=0;
			if(n==0)
				break;
			for(int i=0;i<n;i++){
				tot+=scn.nextInt();
				if(tot<0)
					tot=0;
				if(tot>max)
					max=tot;
			}
			if(max!=0)
				System.out.printf("The maximum winning streak is %d.\n",max);
			else
				System.out.printf("Losing streak.\n");
		}
	}
	/* 
    題目：Q10684 : The jackpot
    作者：1010
    時間：西元 2016 年 8 月 */
}