[알고리즘] 연속 펄스 부분 수열의 합 - 161988

코드: https://github.com/ddalkyTokky/Algorithm_test/tree/main/Python3/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/3/161988.%E2%80%85%EC%97%B0%EC%86%8D%E2%80%85%ED%8E%84%EC%8A%A4%E2%80%85%EB%B6%80%EB%B6%84%E2%80%85%EC%88%98%EC%97%B4%EC%9D%98%E2%80%85%ED%95%A9

1. 부분합

옛날에 남의 풀이를 보고도 못 풀었던 문제다...

근데 지금 다시 보니까 이딴걸 왜 못풀었지..? 라는 자괴감이 몰려온다..

 

부분합에 대한 원리만 알면 간단하다.

딱 두번만 주어진 문자열을 순회하면 된다!

 

첫번째는 순회는 [1, -1, 1 ... ] 을 적용하면서,

두번째 순회는 [-1, 1, -1 ... ] 을 적용하면서,

부분합중 최댓값을 구하면 끝이다!

2. 최종 코드

def solution(sequence):
    answer = 0
    
    partial_sum = [sequence[0]]
    flag = 0
    for idx in range(1, len(sequence)):
        current = sequence[idx]
        if(flag == 0):
            current *= -1
        if(partial_sum[-1] < 1):
            partial_sum.append(current)
        else:
            partial_sum.append(current + partial_sum[-1])
        flag = 1 - flag
    answer = max(partial_sum)
    
    partial_sum = [-sequence[0]]
    flag = 1
    for idx in range(1, len(sequence)):
        current = sequence[idx]
        if(flag == 0):
            current *= -1
        if(partial_sum[-1] < 1):
            partial_sum.append(current)
        else:
            partial_sum.append(current + partial_sum[-1])
        flag = 1 - flag
    if(answer < max(partial_sum)):
        answer = max(partial_sum)
    
    return answer

3. 시간 복잡도

행위	시간 복잡도
순회	O(2N)
최종	O(N)