算法-分治最大子序和问题

分治

分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

可以使用分治法求解的一些经典问题

1. 二分搜索
2. 大整数乘法
3. Strassen矩阵乘法
4. 棋盘覆盖
5. 合并排序
6. 快速排序
7. 线性时间选择
8. 最接近点对问题
9. 循环赛日程表
10. 汉诺塔

53. 最大子序和

package com.company;

public class fenzhi {

  public static void main(String[] args) {
//    int[] temp = {-1,-2,-5,-4,-5,-6,-7,-1};
    int[] temp = {8,-19,5,-4,20};
    System.out.println("最终结果 : " + maxSubArray(temp));
  }

  public static int maxSubArray(int[] nums) {
    return findSubsequence(0,nums.length - 1,nums);
  }

  // 计算resul数组
  // begin : 数组最开始的索引
  // end : 数组最后的索引
  // 最大正子序列和
  public static int findSubsequence(int begin , int end , int[] result) {
    if (begin < 0 || end < 0) return 0;
    // 数组就只有一个元素, 也就是begin = end,
    if (end - begin == 0) return result[begin];


    // 数组有2个及以上的元素

    // 求出中间值
    // 0, 1, 2, 3, 4, 5, 6,
    // 如果当前 begin = 0, end = 1; mid = 1     [0] [1]                   left (begin,begin + mid - 1)  right(begin + mid,end)
    // 如果当前 begin = 0, end = 2; mid = 1     [0] [1,2]                 left (begin,begin + mid - 1)  right(begin + mid,end)
    // 如果当前 begin = 0, end = 3; mid = 2     [0,1] [2,3]               left (begin,begin + mid - 1)  right(begin + mid,end)
    // 如果当前 begin = 0, end = 4; mid = 2     [0,1] [2,3,4]             left (begin,begin + mid - 1)  right(begin + mid,end)
    // 如果当前 begin = 0, end = 5; mid = 3     [0,1,2] [3,4,5]           left (begin,begin + mid - 1)  right(begin + mid,end)
    // 如果当前 begin = 0, end = 6; mid = 3     [0,1,2] [3,4,5,6]         left (begin,begin + mid - 1)  right(begin + mid,end)
    // 如果当前 begin = 0, end = 7; mid = 4     [0,1,2,3] [4,5,6,7]       left (begin,begin + mid - 1)  right(begin + mid,end)
    int mid = (end - begin + 1) >> 1 ;

    // ==============================================
    // 计算中间区间的最大值
    // 从中间往左相加 左边 [begin, mid)
    int leftMax = result[begin + mid - 1];
    int leftSum = 0;
    for (int i = begin + mid - 1; i >= begin ; i--) {
      leftSum = leftSum + result[I];
      if (leftSum > leftMax) {
        leftMax = leftSum ;
      }
    }

    // 从右边往左相加 右边 [mid, end]
    int rightMax =  result[begin + mid ];
    int rightSum = 0;
    for (int i = begin + mid ; i <= end ; i++) {
      rightSum = rightSum + result[I];
      if (rightSum > rightMax) {
        rightMax = rightSum ;
      }
    }
    int midMax = leftMax + rightMax;

    // ==============================================
    // 递归计算左边区间的最大值
    int leftEdgeMax = findSubsequence(begin, begin + mid - 1, result);

    // 递归计算右边区间的最大值
    int rightEdgeMax = findSubsequence(begin + mid , end, result);

    // 最终结果
    int res = rightEdgeMax > leftEdgeMax ? rightEdgeMax : leftEdgeMax;
    res = midMax > res ? midMax : res;
    return res;
  }
}

PS : 这里注意每一段的区间的begin, mid, end三者的对应关系

输出 :

最终结果 : 21

复杂度分析 :

两个for循环: 2 * O(n/2)
两个递归 : 2 * O(logn);

LeetCode结果:

LeetCode

思路 :
分为三部分, 左边部分, 右边部分, 中间向左和右延伸部分

思路