实现以获得最大积分的逻辑

Question

我正在尝试解决我之前发布的这个问题：计算获得的最大积分

示例 有 n = 3 个 sprint，每个 sprint 的天数为 days = [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(sum(arr) * k)，其中 n 是输入数组的大小。我正在寻找更好的方法来减少时间复杂度。

Answer 1

首先迭代数组并计算

sum

和

score

，得分为

arr[i] * (arr[i] + 1) / 2

之和。然后将

total

分数设置为

k / sum * score

（整数除法）和

k = k % sum

。

k

现在处于 0 到 sum - 1 的范围内，这使得它变得更容易，并且如果

k

比

sum

大很多，这一点很重要。

在此标准化之后，您可以使用滑动窗口遍历数组。一种简单的方法将采用 O(sum(arr))，这仍然比暴力破解 O(k*sum(arr)) 好，但并不令人印象深刻。关键是要看到，只要窗口的开始和结束没有改变它们的冲刺，分数就会以恒定的速度变化（这是因为，只要窗口中掉出的那一天的分数总是加 1）因为我们处于同一个冲刺中，进入窗口的那一天也是如此），所以我们可以直接跳到较早结束的冲刺的末尾，并以更大的步长移动滑动窗口，而不是一次只移动一天。变化率是窗口边界天数之间的差异，将其与当前分数相加，然后与最佳分数进行比较，然后重复，直到窗口的开始到达数组的末尾（结束窗户的周围环绕）。

这会产生独立于 k 且存储时间为 O(1) 的 O(n) 解决方案。