最大子数组和问题的两种解法

问题描述

给定一数组,求出此数组的最大连续子数组中元素之和

样例

INPUT

-5, -4, 5, 3, 2, 6, -1, -2, 6, -9

OUTPUT

22

分治解法

最大子数组可能有三种情况:

  1. 最大子数组完全位于中点左边
  2. 最大子数组完全位于中点右边
  3. 最大子数组跨越中点

因此我们可以采取分治法,逐步将问题分解。

 

不难看出,对于前两种情况,我们可以将其视为”求一个更小数组上的最大子数组”问题。所以,不断进行递归调用直到数组大小为1即可解决前两种情况。

 

对于第三种情况,由于已知最大子数组必定跨越中点,而且一定是连续的,所以我们可以分别求出以中点为端点的左右两部分的最大子数组之和,再相加,就得到第三种情况的解。

 

代码和注释如下:

 

[/crayon]

}

//找最大子数组
//分为三种情况:
//1、最大子数组完全位于中点左边
//2、最大子数组完全位于中点右边
//3、最大子数组跨越中点
//前两种情况可以递归调用此函数,当be大于等于en时结束递归
//第三种情况调用findMaxCrossArra()函数解决
//最后调用findMaxInThree()返回三种情况的最大值,即为最大子数组的和
int findMaxSubArray(int a[], int be, int en)
{
if (be >= en) return a[en];

[/crayon]

}

int main()
{
int test[10] = {
-5, -4, 5, 3, 2, 6, -1, -2, 6, -9
};

[/crayon]

}

 

 

动态规划解法

 


此问题还有渐进时间复杂度为O(n)的动态规划解法。

 

代码和注释如下:

 

[/crayon]

}

 

吃桔子的攻城狮

修炼ing……

在 “最大子数组和问题的两种解法” 上有 1 条评论

发表评论