Как вернуть максимальный подмассив в алгоритме Кадане?

Question

public class Kadane {
  double maxSubarray(double[] a) {
    double max_so_far = 0;
    double max_ending_here = 0;

    for(int i = 0; i < a.length; i++) {
      max_ending_here = Math.max(0, max_ending_here + a[i]);
      max_so_far = Math.max(max_so_far, max_ending_here);
    }
    return max_so_far;
  }
}

Приведенный выше код возвращает сумму максимального подмассива.

Как мне вместо этого вернуть подмассив с максимальной суммой?

Answer 1

Примерно так:

public class Kadane {
  double[] maxSubarray(double[] a) {
    double max_so_far = 0;
    double max_ending_here = 0;
    int max_start_index = 0;
    int startIndex = 0;
    int max_end_index = -1;

    for(int i = 0; i < a.length; i++) {
      if(0 > max_ending_here +a[i]) {
        startIndex = i+1;
        max_ending_here = 0;
      }
      else {
        max_ending_here += a[i];
      }

      if(max_ending_here > max_so_far) {
        max_so_far = max_ending_here;
        max_start_index = startIndex;
        max_end_index = i;
      }
    }

    if(max_start_index <= max_end_index) {
      return Arrays.copyOfRange(a, max_start_index, max_end_index+1);
    }

    return null;
  }
}

Answer 2

Приведенный выше код содержит ошибку.Должно быть:

max_ending_here = Math.max(a[i], max_ending_here + a[i]);

NOT:

max_ending_here = Math.max(0, max_ending_here + a[i]);

Если нет, произойдет сбой для последовательности, такой как: 2, 4, 22, 19, -48, -5, 20,40 и верните 55 вместо правильного ответа 60.

СМ. Алгоритм Кадане в http://en.wikipedia.org/wiki/Maximum_subarray_problem

Answer 3

Обновлять вероятный левый (начальный) индекс каждый раз, когда инициируется новая сумма подмассива. Обновите последний левый и правый (конец) после обновления max_sum. Также поддерживайте триггер, который сообщает, создана ли новая сумма подмассива.

int last = 0;
    int sum  = Integer.MIN_VALUE;
    boolean fOrReset = true;
    int _L = -1, L = -1, R = -1;

    for (int j = 0; j < arr.length; j++) {
        last += arr[j];
        if (fOrReset) {
            _L = j+1;
        }
        fOrReset = false;
        if (sum < last) {
            sum = last;
            L = _L;
            R = j+1;
        }
        if (last < 0) {
            last = 0;
            fOrReset = true;
        }
    }

Answer 4

мы можем отслеживать максимальный подмассив, используя следующий код:

import java.util.Arrays;

public class KadaneSolution4MaxSubArray{

    public static void main(String[]args){
        int [] array = new int[]{13,-3,-25,20 ,-3 ,-16,-23,18,20,-7,12,-5,-22,15,-4,7};

        int[] maxSubArray = maxSubArrayUsingKadaneSol(array);
        for(int e : maxSubArray){
                System.out.print(e+"\t");
            }
        System.out.println();
    }

    public static int[] maxSubArrayUsingKadaneSol(int array[]){
        long maxSoFar =array[0];
        long maxEndingHere =array[0];
        int startIndex = 0;
        int endIndex =0;
        int j=1;
        for(; j< array.length ;j++){
            int val = array[j];
            if(val >= val+maxEndingHere){
                    maxEndingHere = val;
                    startIndex = j;
                }else {
                    maxEndingHere += val;
                    };
            if(maxSoFar < maxEndingHere){
                    maxSoFar = maxEndingHere;
                    endIndex = j;
                }
            }

            return Arrays.copyOfRange(array,startIndex,endIndex+1);
    }   
}

PS Предположим, что данный массив является кандидатом на проблему с максимальным подмассивом, а также что все элементы не являются отрицательными

Answer 5

Более простой подход тесно связан с алгоритмом.

int main()
{
   int a[]={-2, 1, -3, 4, -1, 2, 1, -5, 4};
   int size=sizeof(a)/sizeof(a[0]);
   int startIndex=0,endIndex=0,i,j;
   int max_so_far=0,max_sum=-999;
   for(i=0;i<size;i++)
   {
   max_so_far=max_so_far+a[i];//kadane's algorithm step 1
   if(max_so_far>max_sum) //computing max
   {
      max_sum=max_so_far;
      endIndex=i;
   }

   if(max_so_far<0)
   {
   max_so_far=0;
   startIndex=i+1;
   }
}
   cout<<max_so_far<<" "<<startIndex<<" "<<endIndex;
   getchar();
   return 0;
}

Как только у вас есть начальный и конечный индексы.

for(i=startIndex;i<=endIndex;i++)
{
cout<<a[i];
}

Answer 6

Я сохраняю max_so_far в списке:

for(int i = 0;i<N;i++){
    max_end_here = Math.max(seq[i], max_end_here + seq[i]);
    sum_list.add(max_end_here);
    // System.out.println(max_end_here);
    max_so_far = Math.max(max_so_far, max_end_here);
}

Затем ищем самую большую сумму в списке, ее индекс как конец подпоследовательности.Начните с индекса как конец и выполните поиск в обратном направлении, найдите последний индекс с положительным значением.Начало подпоследовательности - это индекс.

for(int i=sum_list.size()-1; i>=0; i--){
    if(sum_list.get(i) == max_so_far){
        end = i;
        while(sum_list.get(i) > 0 && i>=0){
            i--;
        }
        start = (i==-1)?0:i+1;
        break;
    }
}