04. 연속 부분 최대합제가 생각한 간단한 빠른 풀이법

배현우
2021-10-28
조회수 557

우선 아직 정답 공개가 안되어서 이 풀이가 옳지 않을 수 있다는 점 알려드려요.

이런 문제가 나온다면 5번까지 감사합니다 하고 빠르게 맞춰 줘야 할 것 같습니다.

1,2,3번 같은 경우 사실 눈으로 풀어도 문제가 없을 것 같고

4, 5번 특히 5번을 보시면

1 8 3 2 7 -20 3 -5 8 -22 -30 20 8 7 -10 5 -2 9 5 41 -30 11 15 9 2 4 -7 3 -1 -2 5 -6 8

이렇게나 숫자가 많습니다. 일일이 최대값을 적어가며 계산하다가 생각한것은 

어차피 어느 지점에서 수열의 값들을 더해가든 상관없기 때문에 

앞의 양수값들의 합이  가장 가까운 음수보다 크다면 그 값을 살려가고 적다면 그 음수

이전의 숫자들은 무시하고 다음 양수부터 다시 계산해나가는 방식으로 풀면 되겠다는 것입니다.


예를 들어 순서대로 1+8+3+2+7 의 값은 21이죠. 바로 뒤의 값인 -20 보다 1이 크므로 일단 살립니다.

그 뒤에 보시면 3-5 = -2 ,이고 게다가  -22 -30 붙어 나오므로 앞의 값들은 다 무시하면 됩니다.

-30 다음 수인 20부터 시작한다면 20+8+7 -10 = 25 , 5-2 = 3 , 9+5+41-30 =25 

11+15+9+2+4 -7 = 34 , 3-1-2=0  , 5-6+8= 7  각각의 값이 다 양수이므로 다 더해주면 최종값이 됩니다. 


주의해야 할 점은 시작점에서 끝나는 지점까지 항상 연속해서 더해야 하는 점인 것 같고 보기가 더 복잡하게

나온다면 이 풀이법으로는 계산이 조금  힘들지지 않을까 싶네요.

    

2 1
카카오톡 채널 채팅하기 버튼