11

例如，我们有

{2,2,-1}, 
when k = 0, return -1.
when k = 3, return 3.

这甚至很棘手，因为我们有负数和一个额外的变量 k。k可以是任何值，负数，不要做任何假设。

我无法参考https://en.wikipedia.org/wiki/Maximum_subarray_problem和https://www.youtube.com/watch?v=yCQN096CwWM来解决这个问题。

有谁能够帮我？最好使用 Java 或 JavaScript。

这是最大值（无变量 k）的经典算法 o(n)：

public int maxSubArray(int[] nums) {

        int max = nums[0];
        int tsum = nums[0];
        for(int i=1;i<nums.length;i++){
            tsum = Math.max(tsum+nums[i],nums[i]);
            max = Math.max(max,tsum);
        }

        return max;
    }
4

6 回答 6

13

这是一个 o(nlogn) 解决方案，参考 https://www.quora.com/Given-an-array-of-integers-A-and-an-integer-k-find-a-subarray-that-c​​ontains-最大和受制于约束，即总和小于 k

private int maxSumSubArray(int[] a , int k){

    int max = Integer.MIN_VALUE;
    int sumj = 0;
    TreeSet<Integer> ts = new TreeSet();
    ts.add(0);

    for(int i=0;i<a.length;i++){
        sumj += a[i];
        if (sumj == k) return k;
        Integer gap = ts.ceiling(sumj - k);
        if(gap != null) max = Math.max(max, sumj - gap);
        ts.add(sumj);
    }
    return max;
}
于 2016-08-23T17:03:09.853 回答
1

我受到问题中提到的经典解决方案的影响。这个问题可以简单地通过 o(n^2) 解决方案来解决：

private int maxSumSubArray(int[] a , int k){

    int max = Integer.MIN_VALUE;
    for(int i=0;i<a.length;i++){
        int tsum = 0;
        for(int j=i;j<a.length;j++){
            tsum += a[j];
            if(tsum <= k) max=Math.max(max,tsum);
        }
    }

    return max;
}
于 2016-08-23T16:01:32.777 回答
0

这是一个以 O(n²) 运行的简单算法。

std::array<int, 3> input = {2, 2, -1};
int k = -1;
int sum = 0, largestSum = *std::min_element(input.begin(), input.end()) -1;
int i = 0, j = 0;
int start = 0, end = 0;

while (largestSum != k && i != input.size()) {
    sum += input[j];

    if (sum <= k && sum > largestSum) {
        largestSum = sum;
        start = i;
        end = j;
    }

    ++j;
    if (j == input.size()) {
        ++i;
        j = i;
        sum = 0;
    }
}

那是 C++，但用 Java 或 Javascript 编写应该不难。它基本上会尝试所有可能的总和（有n*(n+1)/2），如果找到 k 则停止。

largestSum必须初始化为足够低的值。由于输入的最小元素可能等于 k，因此我将其减去 1。
start并且end是最终子数组的第一个和最后一个索引。

当然，如果您对输入有任何限制，它可以得到改进。

活生生的例子

于 2016-08-22T16:57:19.793 回答
0

这是 python O(n^2) 中的一个：

def maxsubfunc(arr, k):
  s = 0
  maxsofar = -1
  for i,n in enumerate(arr):
    s += n
    if s <= k:
        maxsofar = max(maxsofar, s)
    else:
        maxnow = s
        for j in range(i):
            maxnow -= arr[j]
            if maxnow < k:
                maxsofar = max(maxnow, maxsofar)
 return maxsofar
于 2020-10-02T23:58:33.780 回答
0

想知道为什么没有人为此讨论基于滑动窗口的解决方案（ O(n) ）。

  1. 使用第一个元素初始化窗口。跟踪窗口的开始索引。
  2. 遍历数组，将当前元素添加到窗口。
  3. 如果 sum 变为 > k，则从 start 减小窗口，直到 sum 变为 <= k。
  4. 检查 sum > maxSumSoFar，设置 maxSumSoFar = sum。

注意 -> 上面算法中的“sum”是当前窗口中元素的总和。

int findMaxSubarraySum(long long arr[], int N, long long K)
{
    long long currSum = arr[0];
    long long maxSum = LLONG_MIN;
    int startIndex = 0;
    if(currSum <= X) maxSum = currSum;
    for(int i=1; i<N; i++){
        currSum += arr[i];
        while(currSum > K && startIndex <= i){
            currSum -= arr[startIndex];
            startIndex++;
        }
        if(currSum <= K) maxSum = max(maxSum, currSum);
    }
    return (int)maxSum;
}
于 2021-03-08T06:32:35.757 回答
0

可以使用简单的滑动窗口来解决。首先继续添加数组元素的总和，如果总和超过 k，则通过从开始减去元素来减少它。这仅在数组具有非负数时才有效。

int curr_sum = arr[0], max_sum = 0, start = 0;

// To find max_sum less than sum
for (int i = 1; i < n; i++) {

    // Update max_sum if it becomes
    // greater than curr_sum
    if (curr_sum <= sum)
       max_sum = max(max_sum, curr_sum);

    // If curr_sum becomes greater than
    // sum subtract starting elements of array
    while (curr_sum + arr[i] > sum && start < i) {
        curr_sum -= arr[start];
        start++;
    }
     
    // Add elements to curr_sum
    curr_sum += arr[i];
}

// Adding an extra check for last subarray
if (curr_sum <= sum)
    max_sum = max(max_sum, curr_sum);

return max_sum;
于 2021-07-03T19:08:24.663 回答