[백준][Java] 1912번 연속합 (DP, 누적합)

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    
    public static void main(String[] args) throws IOException{
        int n = stoi(br.readLine());
        
        String[] str = br.readLine().split(" ");
        int[] DP = new int[n+1];
        int max = Integer.MIN_VALUE;
        for(int i=1; i<=n; i++) {
            int num = stoi(str[i-1]);
            DP[i] = (DP[i-1] + num > num)? DP[i-1] + num : num;
            max = Math.max(max,DP[i]);
        }
        System.out.println(max);
        
        
        
        
//        bw.write(sBuilder.toString());
//        bw.flush(); 
//        bw.close();
    }
    
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
    
}

 

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    
    public static void main(String[] args) throws IOException{
        int n = stoi(br.readLine());
        
        String[] str = br.readLine().split(" ");
        int[] DP = new int[n+1];
        int max = Integer.MIN_VALUE;
        for(int i=1; i<=n; i++) {
            int num = stoi(str[i-1]);
//            DP[i] = (DP[i-1] + num > 0)? DP[i-1] + num : 0;
            if(DP[i-1]<0 && num>=0) 
                DP[i] = num;
            else if(DP[i-1]<0 && num<0) { 
                DP[i]=(DP[i-1]>num)? DP[i-1] : num;
            }
            else
                DP[i] = DP[i-1] + num;
            
            max = Math.max(max,DP[i]);
        }
        System.out.println(max);
        
        
        
        
//        bw.write(sBuilder.toString());
//        bw.flush(); 
//        bw.close();
    }
    
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
    
}