największa suma sąsiadujących subarray nie większy niż k

Question

na przykład mamy

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

to nawet trudne, ponieważ mamy liczb ujemnych i dodatkową zmienną k. k może być dowolną wartością, ujemną, nie należy przyjmować żadnych założeń.

Nie mogę się odwołać do https://en.wikipedia.org/wiki/Maximum_subarray_problem i https://www.youtube.com/watch?v=yCQN096CwWM, aby rozwiązać ten problem.

Czy jakiekolwiek ciało może mi pomóc? Lepiej wykorzystaj Javę lub JavaScript.

Oto klasycznego algorytmu O (n) do maksimum (nie zmienną 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

To rozwiązanie O (nlogn) określone 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

tutaj to naiwny algorytm, który działa w 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; 
    } 
} 

To jest C++, ale nie powinno być trudno pisać w Javie lub Javascript. W zasadzie próbuje każdej możliwej sumy (są n*(n+1)/2) i zatrzymuje się, jeśli znajdzie k.

largestSum musi być zainicjalizowany do wartości niskiej dostatecznej. Ponieważ minimalny element wejścia może równać się k, odjęto od niego 1.
start i end są pierwszymi i ostatnimi indeksami ostatniej podtablicy.

Oczywiście można go było poprawić, gdyby istniały jakiekolwiek ograniczenia dotyczące danych wejściowych.

Live example

Answer 3

byłem pod wpływem klasycznego rozwiązania, o którym mowa w pytaniu. Problem ten może być tylko rozwiązany przez O (N^2) Roztwór:

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