Programmers - 연속 펄스 부분 수열의 합 with JAVA

 

 

로직

1. 1,-1,1,-1,1,-1 ....   ,   -1,1,-1,1,-1,1 을 곱한 수열을 각각 판단한다.

2. DP를 활용해 최댓값을 구한다.

3. 두가지 수열이 가질 수 있는 각각의 최댓값 중 큰 값을 반환한다.

 

메인 아이디어 : "DP, 현재 수의 앞의 있는 값들의 합이 음수라면 고려하지 않는다. 즉, 연속 집합에서 앞의 집합의 합이 음수라면 더이상 지금의 집합부터는 더 큰수를 만들 수 없으니 버린다."

 

예를 들어, 1에서 곱한 값이 아래와 같다고 가정하자.

11, -3, -6, -1, 3, 1, 2, -4

[11] -> Max = 11, sum = 11

[11, -3] -> Max = 11, sum =8

[11, -3, -6] -> Max = 11, sum = 2

[11, -3, -6, -1] -> Max = 11, sum = 1

[11, -3, -6, -1, 3] -> Max = 11, sum = 4

(해당 경우는 3의 입장에서 앞에 있는 모든 수를 합해야 본인을 합쳐 더 큰 수를 만들 수 있다.)

 

2, -3, -6, -1, 3, 1, 2, -4

[2] -> Max = 2, sum = 2

[2, -3] -> Max = 2, sum = -1

(이때는 다음 수에 -1을 더하면 더 큰수를 만들 수 없기때문에 이 순간에는 sum을 0 처리한다.)

 

 

 

코드

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        long purse1 = 0;
        long purse2 = 0;
        boolean isPlus = false;
        for(int now : sequence){
            purse1 += (isPlus) ? now : -now;
            purse2 += (!isPlus) ? now : -now;
            purse1 = Math.max(purse1, 0);
            purse2 = Math.max(purse2, 0);
            answer = Math.max(answer, purse1);
            answer = Math.max(answer, purse2);  
            isPlus = !isPlus;
        }
        return answer;
    }
}

 

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        long result1 = 0;
        long result2 = 0;
        boolean index = true;
        for(int num : sequence){
            result1 += (index) ? num : -num;
            result2 += (index) ? -num : num;
            if(result1 >= 0){
                answer = Math.max(answer, result1);
            }
            else{
                result1 = 0;
            }
            if(result2 >= 0){
                answer = Math.max(answer, result2);
            }
            else{
                result2 = 0;
            }
            index = !index;
        }
        return answer;
    }
}