最大的连片子阵的总和大小不大于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; 
    } 

Answer 1

这是称为 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]; 
     Integer gap = ts.ceiling(sumj - k); 
     if(gap != null) max = Math.max(max, sumj - gap); 
     ts.add(sumj); 
    } 
} 

Answer 2

下面是在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是最终子阵列的第一个和最后一个索引。

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

Live example

Answer 3

我被这个问题所提到的经典解决方案的影响。 这个问题可以通过一个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; 
}