andy6804tw
8/6/2016 - 8:41 AM

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23212 這題使用貪婪法,累積總和遇到負數歸零,時間複雜度O(N)

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

這題使用貪婪法,累積總和遇到負數歸零,時間複雜度O(N)

#include<stdio.h>
int main(){
	int n;
	 while (scanf("%d",&n)!=EOF) {
	 		if(n==0)
				break;
			int arr[n],max=0,i,tot=0;
			for(i=0;i<n;i++)
				scanf("%d",&arr[i]);
			for(i=0;i<n;i++){
				tot+=arr[i];
				if(tot<0)
				tot=0;
				if(tot>max)
				max=tot;
			}
			printf("%d\n",max);	
		}
		

/* 
    題目:2014 闖關組 [Problem B5-易中] Apple trees in a line
    作者:1010
    時間:西元 2016 年 8 月 */
}