前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >分治法解决最大子数组问题

分治法解决最大子数组问题

作者头像
Christal_R
发布2019-09-11 15:34:09
1.3K0
发布2019-09-11 15:34:09
举报
文章被收录于专栏:女程序员的日常

问题:输入一个整形数组(有正数也有负数),数组中连续的、一个或多个元素组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。

输入:测试数组1, -2, 3, 10, -4, 7, 2, -5;

输出:最大子数组为3, 10, -4, 7, 2;

   输出最大子数组的和为18 。

1.蛮力法求解

总体思路:

  蛮力法是最简单的实现方法,只要列出数组所有可能的组合,然后找出其中和最大的组合即可;

  蛮力法分三层循环实现:

    1)第一层循环用于固定子数组的起始位置;

    2)第二层循环用于确定子数组的结束位置;

    3)第三层循环用于子数组和的计算,从子数组的头开始遍历到其尾,累加起来就是该子数组的和。

代码实现:
代码语言:javascript
复制
 1 int ForseMax(int *arry,int n,int &_start,int &_end)
 2 {
 3     int i,j,k;
 4     int sum;//用于求和
 5     int _max=MIN;//记录最大和
 6     for(i=0;i<n;i++)
 7     {
 8         for(j=i;j<n;j++)
 9         {
10             sum=0;
11             for(k=i;k<j;k++)
12             {
13                 sum+=arry[k];
14             }
15             if(sum>_max)
16             {
17                 _start=i;//子数组开始处
18                 _end=j;//子数组结尾处
19                 _max=sum;
20             }
21         }
22     }
23     return _max;//返回最大和
24 }

2.分治法求解

总体思路:

  分治法的精髓:

    1)分--将问题分解为规模更小的子问题;

    2)治--将这些规模更小的子问题逐个击破;

    3)合--将已解决的子问题合并,最终得出“母”问题的解;

  所以原数组的最大子数组求法:

    1)分--将原数组拆分成两部分,每个部分再拆分成新的两部分......直到数组被分得只剩下一个元素;

    2)治--每个小型的数组找最大子数组,只有一个元素的数组,解就是该元素;

    3)合--将两个小型数组合并为一个数组,其中解有三种可能:

      • 左边的返回值大,
      • 右边的返回值大,
      • 中间存在一个更大的子数组和;

     返回值应选最大的;

模块实现:
代码语言:javascript
复制
 1 int Divide(int *arry,int l,int r)
 2 {
 3     if(l==r)//只有一个元素时,返回该元素
 4         return arry[l];
 5     else
 6     {
 7         int m=(l+r)/2;
 8         int l_max=MIN,r_max=MIN,m_max=MIN;
 9         l_max=Divide(arry,l,m);//左边和的最大值
10         r_max=Divide(arry,m+1,r);//右边和的最大值
11         m_max=MiddleMax(arry,l,r,m);//中间和的最大值
12         //返回三个值中最大的一个
13         if(l_max>=r_max && l_max>=m_max)
14             return l_max;
15         else if(r_max>=l_max && r_max>=m_max)
16             return r_max;
17         else
18             return m_max;
19     }
20 }
难点解说:

  其中难点在于两个数组合并的时候,位于两个数组中间位置存在最大和的情况,处理方法为:

从中间位置开始,分别向左和向右两个方向进行操作,通过累加找到两个方向的最大和,分别为l_max和r_max,因此存在于中间的最大和为(l_max+r_max);

  向左的累加操作和向右的累加操作完全一样,只需要一层循环就可以解决问题:

  1)初始化l_max、r_max为最小值,命sum=0用于累加;

  2)在向左累加的操作中,sum从中点开始向左逐个累加,累加完一个元素后与l_max相比,l_max保留值较大的一个;

  3)等遍历完左边部分l_max的值得以确认,并用同样的方法确认r_max的值;

  4)最后返回(l_max+r_max)的值。

  具体代码实现如下:

代码语言:javascript
复制
 1 int MiddleMax(int *arry,int l,int r,int m)
 2 {
 3     int l_max=MIN,r_max=MIN;//分别用于记录左、右方向累加的最大和
 4     int i;
 5     int sum;//用于求和
 6     sum=0;
 7     for(i=m;i>=l;i--)//中线开始向左寻找
 8     {
 9         sum+=arry[i];
10         if(sum>l_max)
11             l_max=sum;
12     }
13     sum=0;
14     for(i=m+1;i<r;i++)//中线开始向右寻找
15     {
16         sum+=arry[i];
17         if(sum>r_max)
18             r_max=sum;
19     }
20     return (l_max+r_max);//返回左右之和
21 }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-03-28 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1.蛮力法求解
  • 2.分治法求解
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档