连续子数组的最大和不大于 k

Question

例如，我们有

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

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

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

任何人都可以帮助我吗？最好使用 Java 或 JavaScript.

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

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;
    }

Answer 1

这是一个在 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 或 Java 脚本编写应该不难。它基本上会尝试所有可能的总和（有 n*(n+1)/2）并在找到 k.

时停止

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

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

Live example

Answer 2

受题中经典方案的影响。这个问题可以简单地用一个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;
}

Answer 3

这是一个o(nlogn)的解 https://www.quora.com/Given-an-array-of-integers-A-and-an-integer-k-find-a-subarray-that-contains-the-largest-sum-subject-to-a-constraint-that-the-sum-is-less-than-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;
}

Answer 4

这是 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

Answer 5

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

用第一个元素初始化 window。跟踪 window.
遍历数组，将当前元素添加到 window。
如果总和变为 > k，则从开始减少 window，直到总和变为 <= k。
检查 sum > maxSumSoFar，设置 maxSumSoFar = sum.

注意->上面算法中的'sum'是当前window中元素的总和。

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;
}

Answer 6

可以使用简单的滑动来解决window。首先继续添加数组元素的总和，如果总和超过 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;

连续子数组的最大和不大于 k

largest sum of contiguous subarray No Larger than k

algorithm

queue

dynamic-programming

binary-search

kadanes-algorithm