[Refresh ! 코딩 테스트 / js] -연속 펄스 부분 수열의 합

문제해석

• 처음에는 연속 펄스 부분 수열의 합 이라고 하길래. 펄스 수열 1 ,-1 ,1 or -1,1,-1의 형태를 유지하는 순서들의 합중. 가장 큰수를 return 하시오 라고 생각해서 문제를 풀었는데 처음부터 접근 방법이 잘못되었다는것을 몇번 틀리고 남들의 코드를 보고 나서 깨닫게 되었다.

나의 풀이

• 시간 초과난 코드

function solution(sequence) {
  //1 -1 1 -l 을 곱한 sequence 의 부분합중에 큰수 를 찾거나 
    // -1 1 -1 1 을곱한 sequence 의 부분합중에 큰수를 찾는문제이다. 
     let dp=Array(sequence.length).fill(0);
     let dp2= Array(sequence.length).fill(0);
      dp[0]=sequence[0];
      dp2[0]= sequence[0]*-1;
     let start=1;
     let start2=-1;
    for(var i=1; i<sequence.length; i++){
        start*=-1;
        start2*=-1;
        let hey=sequence[i]*start;
        let hey2= sequence[i]*start2 ;
        dp[i]= Math.max(hey , dp[i-1]+hey)
        dp2[i]= Math.max(hey2, dp2[i-1]+hey2)    
      // 여기 두중에 뭐가 가장 큰 수가 될것인지?       
    }
     return Math.max(...dp,...dp2)
}

이풀이는 마지막 2개의 배열 dp 와 dp2 중에 가장 큰수를 골라 return 하시오 였는데 여기서도 o(n) 이 작동하기 때문에 runtime error 시간 초과가 났다.

• 시간 초과 안나고 통과한 코드

function solution(sequence) {
  //1 -1 1 -l 을 곱한 sequence 의 부분합중에 큰수 를 찾거나 
    // -1 1 -1 1 을곱한 sequence 의 부분합중에 큰수를 찾는문제이다. 
    if (sequence.length === 1) return Math.max(sequence[0], sequence[0]*-1);
     let dp=Array(sequence.length).fill(0);
     let dp2= Array(sequence.length).fill(0);
      dp[0]=sequence[0];
      dp2[0]= sequence[0]*-1;
     let start=1;
     let start2=-1;
     let answer=0;
    for(var i=1; i<sequence.length; i++){
        start*=-1;
        start2*=-1;
        let hey=sequence[i]*start;
        let hey2= sequence[i]*start2 ;
        dp[i]= Math.max(hey , dp[i-1]+hey)
        dp2[i]= Math.max(hey2, dp2[i-1]+hey2)    
      // 여기 두중에 뭐가 가장 큰 수가 될것인지?  
        answer= Math.max(dp[i],dp2[i],answer)
    }
    return answer   
}

남의 코드

function solution(sequence) {
  let answer = 0;
  const temp1 = [];
  const temp2 = [];
    
  for (let i = 0; i < sequence.length; i++) {
    if (i === 0) {
      temp1.push(sequence[i]);
      temp2.push(-sequence[i]);
    }
    else if (i % 2 === 0) {
      temp1.push(Math.max(temp1[i - 1] + sequence[i], sequence[i]));
      temp2.push(Math.max(temp2[i - 1] - sequence[i], -sequence[i]));
    }
    else {
      temp1.push(Math.max(temp1[i - 1] - sequence[i], -sequence[i]));
      temp2.push(Math.max(temp2[i - 1] + sequence[i], sequence[i]));
    }
    answer = Math.max(answer, temp1[i], temp2[i]);
  }
  return answer;
}
출처: https://58cjdcns99.tistory.com/entry/JS-연속-펄스-부분-수열의-합 [Just 두 It:티스토리]

• 나의 코드에서는 start=1 start2=-1 으로 설정하고 이 수가 변경되기 하기 위해서 -1 을계속 해서 곱해줬는데 . 이런경우 더 오래걸리는거 같다.