分治算法解最大子序列和问题

最大子序列和问题

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

这是一道经典的算法题，在LeetCode上的编号是53。
本文以这道题为例学习分治算法

分治算法

分治算法的核心是把问题分成两个大致相等的子问题，然后递归对它们求解，这是“分”的部分，在“治”这一阶段将两个子问题的解合并到一起求解。

根据算法的思想，把数组分割成两部分，左半部分和右半部分，最大子序列出现的位置可能在：

• 左半部
• 右半部
• 跨越分割的位置占据左右半部

递归是这个算法里非常重要的一个环节，它把数组划分到最小单元来进行比较

1:[4,-3,5,-2,-1,2,6,-2]
2:[4,-3,5,-2] [-1,2,6,-2]
3:{[4,-3] [5,-2]} {[-1,2] [6,-2]}

把数组分成了四份，每一份只有两个元素。计算的过程是从左到右进行，比较左边元素，右边元素和两个元素之和的大小，取最大值，也就是max(4,-3,(4+(-3)))，结果是4。同理，整个数组的左半部分最大值是6，最大子序列就是4,-3,5。

[4,-3]=4 [5,-2]=5 
[4,-3,5,-2]=6  max(4,5,6)=6

[-1,2]=2 [6,-2]=6
[-1,2,6,-2]=8  max(2,6,8)=8

[4,-3,5,-2,-1,2,6,-2]=11

max(6,8,11)=11

算法实现

下面是用JavaScript实现的分治算法实现

/**
 * 求最大子序列和
 *
 * @param {*} array 目标数组
 * @param {*} left  左边界
 * @param {*} right 右边界
 * @returns
 */
function maxSubSum(array,left,right){
  var maxLeftSum,maxRightSum
  var maxLeftBorderSum,maxRightBorderSum
  var leftBorderSum,rightBorderSum
  var center

  if(left===right){//基准情形
    if(array[left]>0){
      return array[left]
    }
    else{
      return 0
    }
  }

  center=parseInt((left+right)/2)
  maxLeftSum=maxSubSum(array,left,center)
  maxRightSum=maxSubSum(array,center+1,right)

  maxLeftBorderSum=0
  leftBorderSum=0

  for (let i = center; i >=left; i--) {
    leftBorderSum+= array[i];
    if(leftBorderSum>maxLeftBorderSum){
      maxLeftBorderSum=leftBorderSum
    }
  }

  maxRightBorderSum=0
  rightBorderSum=0
  for (let i = center+1; i <=right; i++) {
    rightBorderSum+=array[i]
    if(rightBorderSum>maxRightBorderSum){
      maxRightBorderSum=rightBorderSum
    }
  }
  var maxSum=max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum)
  return maxSum
}

function max3(a,b,c){
  var max=a>b?a:b
  max=max>c?max:c
  return max
}

maxSubSum([4,-3,5,-2,-1,2,6,-2],0,7);

算法复杂度分析

设是求解大小为N的最大子序列和问题所花费的时间。

• 如果，则不用进行递归，只用进行一次简单的比较即可，花费一个时间单元， 这样可直接得出结果，记作。
• 如果。先讨论求解maxLeftSum和maxRightSum的两个递归调用，这两行求解大小为的子序列问题（假设N是偶数），也就是说每个递归各涉及一半的元素，对每个元素都要进行和上一条一样时间的计算，所以每行花费的时间是个时间单位，两个递归加起来就是个时间单位。再看后面的两个for循环，这俩for循环会接触数组中的每一个元素，但循环内部的工作量是常数，时间复杂度为。

经过分析得到两个方程组

为了简化计算，设置两个前提：

• 假设N是2的幂，也就是说我们总是可以把数组分割成包含偶数个子元素的两部分 。
• 用N代替上面的O(N)，因为T(N)最终是用O(N)来表示的，所以这样做不影响最后的结果。

得到方程。
两边同时除以,得到：

这个方程对于任意2的幂都成立，所以下面的方程都是正确的

一共有个方程，所有方程两边相加，消去相同项后得到：

得到最终的结果：
以上的分析基于是2的幂这个假设，如果不满足，方程不成立；当不是2的幂时，需要加入一些复杂的分析，但是大的结果不变。

转载于:https://www.jianshu.com/p/c4d68d0376ad