문제

배열 A, 스타트포인트 s, 무브 m이 주어졌을 때 배열 A의 s부터 m만큼 움직여서 얻을 수 있는 가장 큰 배열합을 구하라.
예) A = [2, 3, 7, 5, 1, 3, 9], s=4, m=6

이 때 인덱스 이동은 4->3->2->3->4->5->6이고 값은 7+5+1+3+9 = 25이다.

분석

• prefix_sum : 0부터 i번째 원소까지의 합으로 구성된 배열
• count_total(pref, left_pos, right_pos) : left_pos부터 right_pos까지의 합
• 첫번째 for loop에서 시작점부터 왼쪽을 점차 늘려가는 방식으로 탐색
• 두번째 for loop에서 시작점부터 오른쪽을 점차 늘려가는 방식으로 탐색
• 두개의 for loop에서 나온 결과중 최대값을 return

코드

const solution = (A, k, m) => {
  let result = Number.NEGATIVE_INFINITY;
  let pref = prefixSum(A);

  for(let i=0; i<= Math.min(m, k); i++){
    let leftPos = k-i;
    let rightPos = Math.min(A.length-1, k+m - 2*i);
    //console.log(leftPos, rightPos);
    let sum = leftPos > 0 ? pref[rightPos]-pref[leftPos-1] : pref[rightPos];
    result = Math.max(result, sum);
  }

  for(let i=0; i<= Math.min(m, A.length- k-1); i++){
    let leftPos = Math.max(0, k - m + 2 * i);
    let rightPos = k+i;
    let sum = leftPos > 0 ? pref[rightPos]-pref[leftPos-1] : pref[rightPos];
    result = Math.max(result, sum);
  }
  
  return result;
}

const prefixSum = A => {
  let sum = 0;
  return A.map(val => {
    sum += val;
    return sum;
  })
}