(백준 알고리즘 문제풀이) 10211번 Maximum Subarray

문제

 

문제 링크

 

문제 접근

• T: 테스트 케이스의 수
• N: 배열의 크기 (1 <= N <= 1000)
• N 다음줄에는 배열
• 첫번째 루프에 배열 0번째부터 i번째 까지 몇개씩 누적합을 구하는지 인덱싱해주기
• 두번째 배열에는 배열의 첫번째 부분은 빼주고 마지막 배열은 더해주면서 ans값과 비교하기

코드

import sys

T = int(sys.stdin.readline())
for _ in range(T):
    N = int(sys.stdin.readline())
    lst = list(map(int, sys.stdin.readline().split()))

    ans = -10000001
    for i in range(1, N+1):
        result = sum(lst[:i])
        if ans < result:
            ans = result
        for j in range(1, N-i+1):
            result = result - lst[j-1] + lst[j+i-1]
            if ans < result:
                ans = result

    print(ans)

느낀점

ans에 -1,000,001을 지정해주는 것을 생각을 못하여 시간이 좀 걸린문제이다.

문제의 조건에도 집중하자