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