728x90
https://school.programmers.co.kr/learn/courses/30/lessons/161988
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
분석
[2, 3, -6, 1, 3, -1, 2, 4]
구간합 최댓값 구하기 = max(누적합리스트) - min(누적합리스트)
sequence 2 3 -6 1 3 -1 2 4 -1 1 펄스 -2 3 6 1 -3 -1 -2 4 -1 1 펄스
누적합-2 1 7 8 5 4 2 6 1 -1 펄스 2 -3 -6 -1 3 1 2 -4 1 -1 펄스
누적합2 -1 -7 -8 -5 -4 -2 -6
풀이
1. 구간합
def solution(sequence):
answer = 0
sumlist = [0]
for i in range(len(sequence)):
sumlist.append(sumlist[-1]+(-1)**i*sequence[i])
return abs(max(sumlist) - min(sumlist))
2. DP
def solution(sequence):
n=len(sequence)
temp1=[sequence[i]*(-1)**(i+1) for i in range(n)] # -1 1 펄스 곱한 리스트
temp2=[sequence[i]*(-1)**i for i in range(n)] # 1 -1 펄스 곱한 리스트
dp1=[0]*n
dp1[0]=temp1[0]
dp2=[0]*n
dp2[0]=temp2[0]
for i in range(1, n):
dp1[i] = max(dp1[i-1]+temp1[i], temp1[i])
dp2[i] = max(dp2[i-1]+temp2[i], temp2[i])
return max(max(dp1), max(dp2))
728x90