문제 링크

프로그래머스 문제

풀이

가장 긴 부분수열의 합을 만들어 낼 수 있다면 쉽게 풀 수 있는 문제!

코드

 function solution(sequence) {
    var answer = 0;

    const arr1 = [] // 첫번째 양수
    const arr2 = [] // 첫번째 음수
    
    for(let i=0; i<sequence.length; i++){
        if(i %2 ===0){
            arr1.push(sequence[i] * 1)
            arr2.push(sequence[i] * -1)
        }else{
            arr1.push(sequence[i] * -1)
            arr2.push(sequence[i] * 1)
        }
    }

    const arr1Max = getMaxSum(arr1)
    const arr2Max = getMaxSum(arr2)
    return arr1Max > arr2Max ? arr1Max : arr2Max;
}
// 가장 긴 부분순열의 합이 필요함, 어케 만들지
// 이중배열로 만들어 볼까?
function getMaxSum(arr){
    let answer = arr[0];
    const dp = new Array(arr.length).fill(0);
    dp[0] = arr[0]
    for(let i=1; i< dp.length; i++){
        dp[i] = Math.max(dp[i-1] + arr[i] , arr[i])
        answer = Math.max(answer , dp[i])
    }
    
    return answer
    
}