【アルゴリズム】最大サブ配列

問題の説明:

                     ，                 。

理解:

         ，                    ，                      。  ，           ：                   ，              ，        。  ，         ，                       ，       。

暴力の解:

               （  ） ，    （   ）    C(2,n)，                      ，             Θ(n2)。             A （A    1 n），A.length  A     ，           ；      ：

BRUTE_FORCE(A)
            i = 1
            sum = -infinity
            for i <= A.length, inc by 1
                j = i
                last_sum = 0
                for j <= A.length, inc by 1
                    last_sum += A[j]
                    if last_sum > sum
                        sum = last_sum
                        start = i
                        end = j
            return (start, end, sum)

JAvaコード実装:

private static void bruteForce(int[] arr) {
  int start = -1, end = -1, max = 0;
  for (int i = 0; i < arr.length; i++) {
    //   lastSum   ,              
  int lastSum = 0;
  for (int j = i; j < arr.length; j++) {
    lastSum += arr[j];
    if (lastSum > max) {
      max = lastSum;
      start = i;
      end = j;
        }
    }
  }
  System.out.println("maxSum = " + max + ", start : " + start + ", end = " + end);
 }

分治解:

        ：     ，     ，     。             ：                  ，     A[1...n]              left[1...mid] right[mid+1...n]，  mid=(1+n)/2    ，      ，               ，          ，             ，              。
  left/right        ，             ，                   O(n)，                  Θ(n2)。             A[mid] A[mid+1]           ，              Θ(n2)   。                 ，        left/right       ，            A[mid] A[mid+1]           ；                     ，                    。
      ，                    O(n)   。        ：
（1）   ：               

 FIND_CROSSING_MAX_SUBARRAY(A, low, mid, high)
                left_sum = -infinity
                sum = 0
                i = mid
                for i >= low, dec by 1
                    sum += A[i]
                    if sum > left_sum
                        left_sum = sum
                        left_index = i
                
                right_sum = -infinity
                sum = 0
                i = mid + 1
                for i <= high, inc by 1
                    sum += A[i]
                    if sum > right_sum
                        right_sum = sum
                        right_index = i
                return (left_index, right_index, left_sum+right_sum)

（2）   ：          

FIND_MAX_SUBARRAY(A, low, high)
                if low == high
                    return (low, high, A[low])
                else
                    mid = down_trunc((low + high) / 2)
                    (left_start, left_end, left_sum) =
                        FIND_MAX_SUBARRAY(A, low, mid)
                    (right_start, right_end, right_sum) =
                        FIND_MAX_SUBARRAY(A, mid+1, high)
                    (cross_start, cross_end, cross_sum) =
                        FIND_CROSSING_MAX_SUBARRAY(A, low, mid, high)
                    
                    if left_sum > right_sum and left_sum > cross_sum
                        return (left_start, left_end, left_sum)
                    else if right_sum > left_sum and right_sum > cross_sum
                        return (right_start, right_end, right_sum)
                    else
                        return (cross_start, cross_end, cross_sum)

上記のアルゴリズムの漸進時間の複雑さはΘ(nlg(n)).JAvaコード実装:

private static int[] findMaxSubArray(int[] arr, int left, int right) {
  //          
 if (left == right) {
    return new int[]{left, right, arr[left]};
  }
  int mid = (left + right) / 2;
  int[] leftResult = findMaxSubArray(arr, left, mid);
  int[] rightResult = findMaxSubArray(arr, mid + 1, right);
  int[] crossingResult = findCrossingMaxSubArray(arr, mid, left, right);
  if (leftResult[2] > rightResult[2] && leftResult[2] > crossingResult[2]) {
    return leftResult;
  } else if (rightResult[2] > leftResult[2] && rightResult[2] > crossingResult[2]) {
    return rightResult;
  } else {
    return crossingResult;
  }
}

private static int[] findCrossingMaxSubArray(int[] arr, int mid, int left, int right) {
  int leftIndex = -1, rightIndex = -1, leftMax = Integer.MIN_VALUE, rightMax = Integer.MIN_VALUE, sum = 0;
  for (int i = mid; i >= left; i--) {
    sum += arr[i];
    if (sum > leftMax) {
      leftIndex = i;
      leftMax = sum;
    }
  }
  sum = 0;
  for (int i = mid + 1; i <= right; i++) {
    sum += arr[i];
    if (sum > rightMax) {
      rightIndex = i;
      rightMax = sum;
    }
  }
  return new int[]{leftIndex, rightIndex, leftMax + rightMax};
}

問題の規模を縮小:
問題の規模を縮小する方法:

      ，           ，             ，             ？                   ，         ，          ，                ，               ，          。                 ：

1.                ：          、                    
2.                    ，                        
3.             ，                          

  1    。
   A[1]   A[i]            （1<=i<=n），  A[i]    ， A[1]+...+A[i-1]>=0。 i<=2 ，      2  。
 i>2 ，     A[1]...A[i] ，          ： A[1]      、 A[i]           A[1] A[i]      ；
   A[i]              ，      A[1] A[i]            ，                            ，                   ，             0，        2   。      2    。
    3，              A[i]  ，  A[i]<0。          A[i]      ，    A[j]  （1<=j1 ，A[j]+...+A[i]     ，  A[1]+...+A[j-1]      0 A[1]+...+A[i]    。      ， A[i]  A[i]                 。
    ，      Θ(n)。          ，      ，        。

 LINEAR_SEARCH_MAX_SUBARRAY(A)
            sum = -infinity
            start = 0
            end = 0

            cur_sum = 0
            cur_start_index = 1

            i = 1
            for i <= A.length, inc by 1
                cur_sum += A[i]
                if cur_sum < 0
                    cur_sum = 0
                    cur_start_index = i + 1
                else
                    if sum < cur_sum
                        sum = cur_sum
                        start = cur_start_index
                        end = i

            return (start, end, sum)

JAvaコードは次のとおりです.

private static int[] linerSearchMaxSubArray(int[] nums) {
  int start = 0;
  int end = 0;
  int max = 0;
  int temp = 0;
  int ts = 0;
  for (int i = 0; i < nums.length; i++) {
    temp += nums[i];
    if (temp < 0) {
      ts = i + 1;
      temp = 0;
    } else {
      if (temp > max) {
        start = ts;
        end = i;
        max = temp;
      }
    }
  }
  return new int[]{start, end, max};
}

参考文章:https://www.cnblogs.com/SyBlog/p/11371922.html#commentform参考書:『アルゴリズム導論』