반응형
import java.util.Scanner;
public class Main{
static public void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//코드....
int arr [] = new int [n+1];
int dp []=new int[n+1];
for(int i=1;i<=n;i++)
arr[i]=sc.nextInt();
dp[0]=-1000;
for(int i=1;i<=n;i++){
//dp[i]=arr[i];
/* 이런식으로 하면 시간복잡도 초과..
for(int j=i+1;j<n;j++) {
sum+=arr[j];
if(sum>max) max=sum;
}
dp[i]=max;
*/
dp[i]=Math.max(dp[i-1]+arr[i],arr[i]);
}
int max=dp[0];
for(int i=0;i<=n;i++){
max=Math.max(dp[i],max);
}
System.out.println(max);
}
}
반응형
댓글