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 月 */
}