Логика, которую нужно реализовать, чтобы получить максимальное количество очков ⇐ JAVA

[Anonymous]

Я пытаюсь решить эту проблему, которую я опубликовал ранее: https://stackoverflow.com/questions/782 ... d/78270606
Пример Есть n = 3 спринта, количество дней каждого спринта равно дням = [2,3,2] и k=4.
Максимальное количество баллов, которое можно набрать = 2+ 1+2+3 = 8.
Один из вариантов — начать в последний день первого спринта и закончить в последний день второго спринта.
Вот мой метод грубой силы, при котором каждый индекс проверяется на предмет получения максимального количества баллов.

Код: Выделить всё

static long solve(int[] arr, int k) {
long maxPoints = 0;
int n = arr.length;
for (int i  = 0; i < n; i++) {
int index = i;
long currentPoints = 0;
int k1 = k;
while (k1 > 0) {
for (int j = arr[index]; j > 0 && k1 > 0; j--, k1--) {
currentPoints += j;
}
index++;
if (index == n) {
index = 0;
}
}
maxPoints = Math.max(maxPoints, currentPoints);
}
return maxPoints;
}

Этот код выполняется с временной сложностью O(n * k), где n — размер входного массива. Я ищу лучший подход, который требует меньше времени.

Подробнее здесь: https://stackoverflow.com/questions/782 ... mum-points