백준 - 연속합

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/1912

 

[문제 설명]

동적프로그래밍으로 연속부분최대곱 문제를 보다가 전에 이거랑 비슷한 문제가 있었다는 생각이 들어서 풀었다.

 

[자바]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
    public static void main(String[] args) throws IOException {
        // 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] numbers = new int[N];
        int index = 0;
        for (String s : br.readLine().split(" ")) numbers[index++] = Integer.parseInt(s);
        int answer = numbers[0];

        for (int i = 0; i < numbers.length-1; i++) {
            if (numbers[i] + numbers[i+1] > numbers[i+1]) numbers[i+1] += numbers[i];
            answer = Math.max(numbers[i+1],answer);
        }
        System.out.println(answer);
    }
}

[파이썬]

N = input()
numbers = input().split(" ")
for i in range(0, len(numbers)):
    numbers[i] = int(numbers[i])
answer = numbers[0]

for i in range(0,len(numbers)-1):
    if (numbers[i]+numbers[i+1] > numbers[i+1]): numbers[i+1] = numbers[i+1] + numbers[i]
    answer = max(answer,numbers[i+1])
print(answer)