[프로그래머스/Level3] 연속 펄스 부분 수열의 합 (JAVA)

📖 문제

프로그래머스

 

 

💡  풀이 방식

• DP

- 연속된 합이 최대가 되도록... → dp

dp[n] : n번째 원소를 포함했을 때의 최댓값
⇒ dp[n] = Math.max(dp[n-1] + n, n)

 

 

 

 

💥 유의사항

- 부분 수열의 합은 절대 0보다 작을 수 없으므로, 0 이하로 값이 나오게 되면 dp를 초기화하고 다시 최댓값을 구한다!

- answer이 long 형으로 선언되어 있으므로, long형으로 계산해야 오류가 나지 않는다.

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        
        boolean isPlus = true;
        
        long p1 = 0;    // [1,-1,1,...] 을 순서대로 곱하는 부분 수열의 합
        long p2 = 0;    // [-1,1,-1,...]을 순서대로 곱하는 부분 수열의 합
        
        for(int num : sequence) {
            p1 += isPlus ? num : -num;
            p2 += isPlus ? -num : num;
            
            // 0보다 값이 작아진 경우, 0으로 만들기 (0보다 더 작은 값이 될 수 없으므로)
            p1 = Math.max(0, p1);
            p2 = Math.max(0, p2);
            
            // p1과 p2가 answer보다 커지면, answer 갱신하기
            answer = Math.max(answer, Math.max(p1, p2));
            
            isPlus = !isPlus;
        }  
        
        return answer;
    }
}

 

 

 

 

➕ 다른 풀이 방식

- 누적합을 활용한 풀이

[프로그래머스] 연속 펄스 부분 수열의 합 JAVA

 

 

- 헐 이거 내가 풀려던 방식과 같다!!!! 개인적으로 이 풀이가 더 이해가 잘 되는 듯

[프로그래머스] 연속 펄스 부분 수열의 합 (자바)

---

💦 어려웠던 점

- dp인 것은 캐치했고 이렇게 풀려고 노력했으나,,, 구현이 제대로 안 된 것 같아서 다른 분 풀이를 보고 작성했다.

- 내가 틀리게 풀었던 방식을 보니 완전 기초 dp 문제라 알아서 가장 큰 값을 저장할텐데 구간을 나누면서 확인하려고 생각했었다... 그러지 않아도 되었는데!!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

[프로그래머스] 연속 펄스 부분 수열의 합 Lv3 JAVA [DP][엄탱]