[콭] 연속 펄스 부분 수열의 합-DP

연속 펄스 부분 수열의 합

문제

다음 주어진 수열과 펄스 수열의 곱의 부분 합의 최대값을 구하여라.

헤맨 부분과 해결

최대값을 sequence를 돌 때마다 구해서 연속된 값의 합을 구하기가 어려웠다.

max=Math.max(sequence[i],sequence[i]+dp[i],max)

예를 들어 [3,1,6] 같은 경우 pulse와의 곱을 구하면 [3,-1,6]이 되어 최대값은 8이 되어야 한다.
그러나 위와 같이 구하면 6이 되어버린다.

따라서 dp[i]에 i까지의 최대 값을 저장하고 dp 중 최대값을 반환하면 된다.

코드

function pulse(sequence, flag) {
  return sequence.map((s) => {
    flag *= -1;
    return s * flag;
  });
}
function pulseMax(ps,len){
    let dp={}
    dp[0]=ps[0] 
    for(let i=1;i<len;i++){
        dp[i]=Math.max(ps[i],ps[i]+dp[i-1]) 
    }
    let val=Object.values(dp).sort((a,b)=>b-a)
    return val[0]
}
function solution(sequence) {
  let answer = 0;
  
  let ps = pulse(sequence, -1);
  let ms = pulse(sequence, 1); 
  answer=Math.max(pulseMax(ps,sequence.length),pulseMax(ms,sequence.length)) 
  
  return answer;
}