백준)Q.1912_연속합

 

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

1912번: 연속합

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

 

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

 

출력

첫째 줄에 답을 출력한다.

 

예제 입력 1 

10

10 -4 3 1 5 6 -35 12 21 -1

 

예제 출력 1 

33

 

나의 풀이 1

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int n = Integer.parseInt(br.readLine());
        String input = br.readLine();
        String[] tmp = input.split(" ");
        int max = Integer.MIN_VALUE;
 
        int[] arr = new int[n];
        for (int i = 0; i < tmp.length; i++) {
            arr[i] = Integer.parseInt(tmp[i]);
        }
 
        for (int i = 0; i < n; i++) {
            int overSum = 0;
            for (int j = i; j < n; j++) {
                overSum += arr[j];
                max = overSum > max ? overSum : max;
            }
        }
 
        System.out.println(max);
    }
 
}

이중루프를 이용해서 속도가 매우x100000 느린 코드다.

주어진 수들을 배열에 넣고 arr[0]부터 arr[n-1]까지 연속적으로 더해서 max값을 계산해주는 방법.  

 

나의 풀이 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
 
        String[] input = br.readLine().split(" ");
 
        int preSum = 0;
        int max = Integer.parseInt(input[0]);
 
        for (int i = 0; i < n; i++) {
            int curr = Integer.parseInt(input[i]);
            if (preSum < 0)
                preSum = curr;
            else
                preSum += curr;
 
            max = max < preSum ? preSum : max;
        }
        System.out.println(max);
    }
 
}

1. max에 맨 첫번째 수를 넣는다.

2. 반복문을 돌며 preSum에 계속 더해간다. 단 이전까지 더한 수(preSum)가 음수면 현재값을 더하지 않고 그냥 preSum에 현재값을 넣는다.

이전값이 음수인 경우 현재값이 음수면 더 작아지고 양수면 현재부터 더해가는게 나으니까!