不大于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 和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;
    }

- Jerry Z.

---

任何复杂度的要求吗？ - Nelfeal

没有更多的要求，你能解决它吗？ - Jerry Z.

子数组的长度或子数组的和不能大于k，那么应该是哪个值呢？对于测试[1, 2, 3]，k = 2，答案是5还是2？ - Nikita Sivukhin

与标题相符，最大连续子数组之和不大于k。 - Jerry Z.

候选迁移到：https://codegolf.stackexchange.com/ - ryanwebjackson

Answer 1

这是一个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;
}

- Jerry Z.

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

- Jerry Z.

Answer 3

这是一个天真的算法，其时间复杂度为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是最终子数组的第一个和最后一个索引。

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

实时示例

- Nelfeal

Answer 4

可以使用简单的滑动窗口来解决。首先不断将数组元素的和相加，如果和超过k，则从开头开始减去元素以使其小于或等于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;

- akshay kumar

Answer 5

# 解决Kadane算法的3个步骤
//方法
sum = 0
maxi = arr [0]
for i = 0到arr.length {
//步骤
1. sum = sum + arr [i]
2. maxi = max（maxi，sum）
3. if（sum＜0） -> sum = 0
}
返回最大值

//解决方案

nums=[-2,1,-3,4,-1,2,1,-5,4]

class Solution {
public int maxSubArray(int[] nums) {
    int sum=0; 
    int maxi=nums[0]; 
    for(int i=0 ; i<nums.length ; i++){ 
        sum+=nums[i]; 
        maxi=Math.max(maxi,sum); 
        if(sum<0){ 
            sum=0; 
        } 
    } 
    return maxi; 
    
} 





  

- Aashutosh Gupta

---

你能提供更多的上下文吗？为什么这个解决方案有效，性能如何，这些信息会很有帮助。 - ryanwebjackson

你能提供一些更多的背景信息吗？解决方案为什么有效，以及性能如何，这些都会很有帮助。 - undefined

请参考LeetCode的解决方案：https://leetcode.com/submissions/detail/887255042/ - Aashutosh Gupta

你可以参考LeetCode的解决方案https://leetcode.com/submissions/detail/887255042/ - undefined

Answer 6

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

1. 使用第一个元素初始化窗口。跟踪窗口起始索引。
2. 遍历数组，将当前元素添加到窗口中。
3. 如果总和变得大于k，则从开始处减小窗口，直到总和小于等于k。
4. 检查如果总和大于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;
} 

- pulkit

---

即使有负数，这个能正常工作吗？ - Fransebas

Answer 7

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

- maindoor