본문 바로가기
개발 관련 공부/알고리즘

백준 1912

by 슴새 2021. 7. 26.
반응형

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);
         
	}
     
 }
반응형

'개발 관련 공부 > 알고리즘' 카테고리의 다른 글

백준 11651  (0) 2021.07.29
백준 2751  (0) 2021.07.28
백준 11054  (0) 2021.07.22
백준 11053  (0) 2021.07.21
백준 11057  (0) 2021.07.20

댓글