在给定列表中查找具有限制的连续范围

Question

查找满足给定条件的最大连续元素。

\n

我有一个名为 A 的数字列表、另一个名为 B 的列表和一个名为 Limit 的限制。

\n

任务是找到 A 中最大的 k 个连续元素，使它们满足以下条件。

\n

\n

最大(B[i],B[i+1],...B[i+k]) + Sum(A[i], A[i+1], ..., A[i+k]) * k \xe2\x89\xa4 限制

\n

\n

例子：

\n

\n

A = [2,1,3,4,5]
\nB = [3,6,1,3,4]
\n限制 = 25

\n

取 2 个连续元素：
\n最高总和出现在 A = 4,5 中的元素处。B 中相应的最大值是 Max(3,4) = 4。
\n所以 value = 4 + (4+5) * 2 = 22。这里 22 \xe2\x89\xa4 25，所以 2 个连续是可能的

\n

取 3 个连续元素：
\n对 A 的前 3 个元素求和 = 2,1,3。B 中相应的最大值是 Max(3,6,1) = 6。
\n所以 value = 6 + (2+1+3) * 3 = 24。这里 24 \xe2\x89\xa4 25，所以 3 个连续是可能的

\n

取 4 个连续元素：
\n对 A 的第 4 个元素求和 = 2,1,3,4。B 中对应的最大值是 Max(3,6,1,3) = 6。
\n所以 value = 6 + (2+1+3+4) * 4 = 46。这里 46 > 25，所以不可能连续 4 个

\n

因此该输入的正确答案是 3。

\n

\n

约束：
\nn（A 的大小）最多为 10\xe2\x81\xb5，A 元素最多为 10\xc2\xb9\xe2\x81\xb4，B 元素最多为 10\xe2\x81\xb9，限制上限到 10\xc2\xb9\xe2\x81\xb4。

\n

这是我的代码：

\n

public int getMax(List<Integer> A, List<Integer> B, long limit) {\n    int result = 0;\n    int n = A.size();\n    for(int len=1; len<=n; len++) {\n        for(int i=0; i<=n-len; i++) {\n            int j=i+len-1;\n            int max = B.get(i);\n            long total = 0;\n            for(int k=i; k<=j; k++) {\n                total += A.get(k);\n                max = Math.max(max, B.get(k));\n            }\n            total = max + total * len;\n            if(total < limit) {\n                result = len;\n                break;\n            }\n        }\n    }\n    return result;\n}\n

\n

此代码适用于较小范围的输入。\n但对于较大的输入会失败并超时。如何降低这段代码的时间复杂度？

\n

更新：

\n

根据dratenik答案更新了代码，但我的帖子中提到的示例测试用例本身失败了。该程序正在返回4而不是3.

\n

public int getMax(List<Integer> A, List<Integer> B, long limit) {\n    int from = 0, to = 0, max = -1;\n    int n = A.size();\n    for (; from < n;) {\n        int total = 0;\n        int m = B.get(from); // updated here\n        for (int i = from; i < to; i++) {\n            total += A.get(i); // updated here\n            m = Math.max(m, B.get(i)); // updated here\n        }\n\n        total = m + total * (to - from); // updated here\n\n        if (total <= limit && to - from + 1 > max) {\n            max = to - from + 1;\n        }\n        if (total < limit && to < n) { // below target, extend window\n            to++;\n        } else { // otherwise contract window\n            from++;\n        }\n        if (from > to) {\n            to = from;\n        }\n    }\n    return max;\n}\n

\n

Answer 1

由于 A 和 B 的所有元素都是正数，因此您可以使用通常的两指针方法来查找最大长度子数组来解决此问题：

1. 将两个指针s和e初始化到数组的开头，然后在不违反限制的情况下将e尽可能前移。这会找到从s开始的最长有效子数组。
2. 当e不在数组末尾时，将s前进一位，然后在不违反限制的情况下再次尽可能远地前进e 。这会找到从每个位置开始的最长有效子数组。这导致了 O(n) 算法，因为e可以单调前进。
3. 您的答案是您看到的最长的有效序列。

为了在 O(1) 中确定从s到e的特定范围是否有效，您需要跟踪 A 元素的累积和以及 B 元素的当前最大值。

求和很简单——只需添加e传递的元素并减去s传递的元素即可。

要跟踪 B 中元素的当前最大值，您可以使用此处描述的标准滑动窗口最大值算法：O(n) 时间内的滑动窗口最大值。它可以很好地扩展和收缩窗口，保持每次操作的摊余成本为 O(1)。

这是 Java 中的 O(n) 解决方案。请注意，我将 A 元素的总和乘以序列的长度，因为这似乎是您想要的，即使您编写的公式乘以 length-1：

public static int getMax(List<Integer> A, List<Integer> B, long limit) {
    final int size = A.size();
    // a Queue containing indexes of elements that may become max in the window
    // they must be monotonically decreasing
    final int maxQ[] = new int[size];
    int maxQstart = 0, maxQend = 0;
    // current valid window start and end
    int s=0, e = 0;
    int bestLen = 0;
    long windowSum = 0;
    while (s < size && e < size) {
        // calculate longer window max
        long nextMax = maxQstart < maxQend ? B.get(maxQ[maxQstart]) : 0;
        nextMax = Math.max(nextMax, B.get(e));
        long sumPart = (windowSum + A.get(e)) * (e+1-s);
        if (nextMax + sumPart <= limit) {
            // extending the window is valid
            int lastB = B.get(e);
            while (maxQstart < maxQend && B.get(maxQ[maxQend-1]) <= lastB) {
                --maxQend;
            }
            maxQ[maxQend++] = e;
            windowSum += A.get(e);
            ++e;
            if (e-s > bestLen) {
                bestLen = e-s;
            }
        } else if (e > s) {
            // extending the window is invalid.
            // move up the start instead
            windowSum -= A.get(s);
            ++s;
            while(maxQstart < maxQend && maxQ[maxQstart] < s) {
                ++maxQstart;
            }
        } else {
            // we need to move the start up, but the window is empty, so move them both
            ++s;
            ++e;
        }
    }
    return bestLen;
}