[프로그래머스] Level 3. 연속 펄스 부분

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

프로그래머스

 

 

해결 방법

1. sequence 에 연속펄스 (-1,1,-1...) 을 곱한 v1 과 , (1,-1,1,..)을 곱한 v2를 만든다.
2. 이 두 배열에 대해 getMax() 함수를 수행하는데, 이 함수는 가능한 연속부분수열 합의 최대값을 찾는함수이다. 
   1. 맨 첫번째 요소부터 더한다. 만약 양수라면, 더하는것이 무조건 이득이므로, sum 을 증가시킨다. (sum이 증가할때 항상 answer을 갱신시도한다)
   2. 만약 음수이고, 지금까지 더했던 값보다도 훨씬 작은수라면, 앞에있는 값들을 모두 버리는게 이득이다. 따라서 sum = 0 으로 초기화하고 넘어간다. 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long answer = 0;

void getMax(vector<int> sequence){
     long long sum = 0;
    for(int i=0; i<sequence.size(); i++){
        
        if(sequence[i] < 0 && sum + sequence[i] <0){
            sum = 0;
            continue;
        }
        
        sum += sequence[i];
        answer = max(sum,answer);
    }
}
long long solution(vector<int> sequence) {
    
    vector<int> v1 = sequence;
    vector<int> v2 = sequence;
    for(int i=0; i<sequence.size(); i++){
        if(i%2 ==0 ) v1[i]*=-1;
        else v2[i] *=-1;
    } 
    
    
    getMax(v1);
    getMax(v2);
    
    return answer;
}