Что нужно сделать в задаче? Что значит выпирающие точки?

Question

[Александр Буки]

Задача с контеста Яндекса:

Писать свой игровой движок с нуля всегда сложно. Но не для Васи! Он потратил уже много времени, чтобы описать графику и физику.
Одна из задач — уменьшение суммы по точкам. Код был написан давно, и Вася не помнит, зачем он вообще был нужен. А если его удалить, то движок совсем перестаёт работать.
Представим, что даётся некоторая последовательность точек и количество операций. Помогите Васе — напишите функцию, которая будет схлопывать массив.
Делать это представляется следующим образом: нужно выпирающие точки обратить (умножить на –1) таким образом, чтобы сумма была минимальной. Выпирающие области обращать можно несколько раз. По минимальной сумме движок будет определять порядок отрисовки.
Раньше разработчик придумал гениальное решение. Всё работает прекрасно. Но, к сожалению, тормозит. Помогите ему решение, которое будет работать быстрее. Текущее решение представлено ниже.

/**  
 * A {number[]} - массив целых чисел  
 * K {number} - количество операций  
 */  
module.exports = function solve ({ A, K }) {  
    if (K === 0) return A.reduce((a, b) => a + b, 0);  
 
    const r = Math.min(...A.map((el, index) => {  
        const a = [...A];  
        a[index] = -el;  
        return solve({ A: a, K: K - 1 });  
    }));  
 
    return r;  
};

Примеры
solve({ A: [ 167, -4893, -3864, 5597 ], K: 2, }); // -14521

solve({ A: [ 2943, -5014, -7766, -5408 ], K: 2, }); // -15245
Формат ввода
На вход подаётся 2 аргумента:

points — массив точек x. Значения внутри него всегда определены и лежат в промежутке -100000 и 100000
operations — максимальное количество обращений x. Всегда выражено числом и лежит в промежутке 1 и 1000000

Я сделал так, но решение не проходит все тесты:

function solve ({ A, K }) {
  A.sort((a, b) => b - a)
  for (let i = 0; i < K; i++) {
    if (A[i] > 0) { A[i] = A[i] * -1 }
  }
  return A.reduce((a, b) => a + b, 0)
}

Не понимаю что значит выпирающие точки, мин и макс?

Comments

[ksnk]

По сути - правильно. Может проблема в том, что исходный массив нельзя менять ? Ну и если ты все равно бежишь по всем элементам массива - почему бы сразу и не посчитать сумму, без финального reduce ?

[ksnk]

В твоем решении не только мутирует исходый массив. Само решение, для случая
solve([1], 10) должно выдавать не -1, как в в твоем случае, а 1, так как ВСЕ указанные обращения надо применить. в этом случае - 10.
Решением было бы для всего количества "обращений" всегда искать максимальное значение, инвертировать его. Оптимизация - если "максимальное значение" отрицательно и осталось четное количество обращений - можно остановиться.

[Александр Буки]

ksnk, да, тоже об этом подумал, попробую пересобрать. Спасибо!

Answer 1

[Александр Буки]

Решение, которое прошло все тесты:

function solve ({ A, K }) {  
    if (K === 0) return A.reduce((a, b) => a + b, 0);  
    A.sort((a,b) => b - a)
    for (i =0; K > 0; i++, K--) {
        if (A[i] > 0) {
            A[i] = -A[i]
        } else {
            break
        }
    }
    A.sort((a,b) => b - a)
    if (K%2 === 1) {
        A[0] = -A[0]
    }
    return A.reduce((a, b) => a + b, 0)
}