배열 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이다.
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;
})
}