프로그래머스 레벨 3 연속 펄스 부분 수열의 합

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/161988#

처음 접근 : 투포인터

처음에 start와 end 포인터를 설정한 후 다음 인덱스가 양수라면 end+1, 아니라면 start+1을 하는 방식으로 접근하였으나 실패.
while문의 탈출 조건과 end+1과 start+1의 기준을 확실히 파악할 수 없어 다른 방식인 누적합/구간합을 활용하여 해결하고자함.

추후에 투포인터 방식으로 또한 해결할 것.

새 접근 : 누적합/구간함

특정 구간 a~b의 합은, b까지의 구간합에서 a까지의 구간합을 뺀 결과와 같다.누적합으로 새로운 배열을 선언해준후, 계산해주면 됨.
이때 특정 인덱스 i까지의 최대 구간의 값을 구하는 법은, i인덱스 까지의 합에서 i인덱스 전까지의 값중 가장 작은 값을 빼주면됨.

전체 코드

import copy
def solution(sequence):
    one=copy.deepcopy(sequence)
    one.insert(0,0)
    num=1
    for i in range(len(one)):
        one[i]*=num
        num*=-1
    for i in range(len(one)-1):
        one[i+1]=one[i]+one[i+1]

    two=copy.deepcopy(sequence)
    two.insert(0,0)
    num=-1
    for i in range(len(two)):
        two[i]*=num
        num*=-1
    for i in range(len(two)-1):
        two[i+1]=two[i]+two[i+1]
        
        
    onemin=100001
    for i in range(len(one)):
        onemin=min(onemin,one[i])
        one[i]=one[i]-onemin
    twomin=100001
    for i in range(len(two)):
        twomin=min(twomin,two[i])
        two[i]=two[i]-twomin
    return max(max(one),max(two))

궁금한거

왜 첫번째 인덱스에 0을 안넣으면 에러가 났을까?

누적합 문제를 풀 때 첫번째 인덱스에 0을 추가해주는 이유는 다음과 같다.
누적합을 처리할 경우 첫번째 원소 이전의 누적합은 0으로 간주되기 때문에, 처음 경계 조건을 따로 처리해주어야함.

맨 처음에 0을 추가하지 않은 코드에선,

for i in range(len(one)):
    onemin=min(onemin,one[i])
    one[i]=one[i]-onemin
이 부분에서 one배열에 0번째 인덱스에 무조건 0이 들어감. 그래서
이처럼 처음 조건을 따로 처리해주지 않았기 때문에 에러가 났던것.

그러므로 누적합 문제를 풀때 맨 앞에 0을 넣어주고 풀도록하자.