andy6804tw
10/4/2016 - 8:14 AM

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=32661 這題就是貪婪法則取最大值每次相加做比對,當tot遇到負數時直接tot=num重新開始連加

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=32661

這題就是貪婪法則取最大值每次相加做比對,當tot遇到負數時直接tot=num重新開始連加

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scn=new Scanner(System.in);
		int n=scn.nextInt();
		while(n--!=0){
			int j=scn.nextInt(),tot=0,max=0;
			for(int i=0;i<j;i++){
				int num=scn.nextInt();
				if(tot<0)
					tot=num;
				else
					tot+=num;
				if(tot>max)
					max=tot;
			}
			System.out.println(max);
		}

	}
/* 
    題目:Problem5. Finding a Maximum Profit Interval for a Long Term Investment
    作者:1010
    時間:西元 2016 年 10 月 */
}