[JAVA] 백준 1912 연속합

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

- n개의 정수로 이루어진 임의의 수열이 주어짐

- 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 함 

- 단, 수는 한 개 이상 선택해야 함

 

ex)

10,-4,3,1,5,6,-35,12,21,-1이라는 수열

정답은 12+21인 33

 

 

문제 풀이 

 

[백준/BOJ] 1912번 연속합 (C/C++) (tistory.com)

[백준/BOJ] 1912번 연속합 (C/C++)

 

3,5,6,-35,12,21,-1

 

- 1번까지의 연속합의 최대값은 [1번째 값(3)]인 3 (3을 memo[ ]에 기록)

 

- 2번까지의 연속합의 최대값은 [직전에 기억한 최대값(3) + 2번째 값(5)]인 8 (8을 memo[ ]에 기록 )

 

- 3번까지의 연속합의 최대값은 [직전에 기억한 최대값(8) + 3번째 값(6)]인 14 (14를 memo[ ]에 기록 )

 

- 4번까지의 연속합의 최대값은 [직전에 기억한 최대값(14) ]인 14

  (직전 최대 (14) + 4번째 값(-35)인 -21을 memo[ ]에 기록)

 

- 5번까지의 연속합의 최대값은 [5번 값(12)]인 12

(12을 memo[ ]에 기록 )

 

- 6번까지의 연속합의 최대값은 [직전에 기억한 최대값(12) + 6번째 값(21)]인 33

(33을 memo[ ]에 기록 )

  

- 7번까지의 연속합의 최대값은 [직전에 기억된 최대값(33) + 7번째 값(-1)]인 32

 

n번까지의 연속합의 최대값은 Math.max( [n-1번까지의 최대값 + n번 값], [n번값]) 

 

 

정답

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main 
{
    static int max;
    static int memo[] = new int[100000];
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        
        int input[] = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<input.length; i++)
        {
            
            input[i] = Integer.parseInt(st.nextToken());
        }
        
        max = input[0];
        memo[0] = input[0];
        
        for(int i=1; i<n;++i)
        {
            memo[i] = Math.max(memo[i-1]+input[i], input[i]);
            max = Math.max(memo[i],max);
        }
        
        bw.write(max+"");
        
        bw.flush();
        bw.close();
    }
    
    
}