[Baekjoon] 10211_Maximum Subarray

Silver III

문제(출처: https://www.acmicpc.net/problem/10211)

---

<Maximum Subarray>

문제 

 

크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분
배열을 찾는 Maximum subarray problem(최대 부분 배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다.
여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하자.
즉, max1 ≤ i ≤  j ≤ N (X [i]+...+X [j])를 구하자.

 

입력

 

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다.
그다음에는 T개의 테스트 케이스가 주어진다.
각 테스트 케이스 별로 첫 번째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000)
그리고 두 번째 줄에 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다.
이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다.

 

출력 

 

각 테스트 케이스 별로 maximum subarray의 합을 줄로 구분하여 출력한다.

 

 

문제 풀이

   - my solution

import sys

if __name__=='__main__':
    T=int(input()) # 테스트 케이스 수

    for i in range(T):
        N=int(input()) # 크기
        arr=list(map(int, sys.stdin.readline().split())) # X의 내용

        maxsum=min(arr) # 최솟값을 maximum으로 설정
        for j in range(len(arr)):
            sum = 0
            for k in range(j,len(arr)):
                sum+=arr[k]
                if sum>maxsum: # maximum subarray 찾기
                    maxsum=sum
        print(maxsum)

 

• Maximum subarray를 구하기 위해 반복문 활용
• 이중 반복문을 활용하여 각 구간마다 maximum인지 확인

---

생각🤔

 

이중 for문을 활용하여 구현하면 시간 초과가 날까 봐 고민했지만, 다른 방법이 떠오르지 않아 처음 생각대로

구현해보았다. 처음에 maxsum을 초기화할 때 0으로 초기화를 잘못해준 것 말고는 다른 문제점이 없었다.

 

---