最大子数组求解

佚名 5年前 (2019-03-01) 算法 1305人围观抢沙发百度已收录

总结一下目前的几种算法：

1：暴力求解：直接组合求解

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

  for (int i = 0; i < array_length; i++)
    {
        for (int j = i ; j < array_length; j++)
        {

            //计算遍历的子数组之和
                subarraysum += A[j];
            //找出最大的子数组
            if (subarraysum>sum)
            {
                sum = subarraysum;
                low = i;
                height = j;
            }
        }
    }

2:分治策略

主要思想：考虑一个子数组a[i...j]的最大子数组可能出现三种情况 a. 出现在a[i..N/2],b.出现在a[N.2...j] ,c.包括a[N/2];

3:算法导论课后思想

主要思想1：利用a[1..i]的最大子数组计算a[1...i+1],可知两种情况 a,与a[1..i]相同，b，包含a[i+1],从后往前循环寻找

主要思想2：a[1:i]有两个数组，其中一个是最大子数组，另外一个是包含a[i]的最大子数组，重写思想1描述的两种情况，对于第二种情况可值分为两种情况 a，只有a[i+1b.为a[1：i]

的极右最大子数组加上a[i+1];

实现如下：

include <iostream>
using namespace std;
int finf_maximux_subaarray( int * array ,int &low,int &high ,int n)
{
low=0;
high=0;
int left_bound=0;
int sum=array[0];
int bound=array[0];
for(int i=1;i<n;i++)
{
  if(bound+array[i]<array[i])
  {
   bound=array[i];
   left_bound=i;
  }
  else
  {
   bound+=array[i];
  }   if(sum<bound)
  {
   low=left_bound;
   high=i;
   sum=bound;
  }
}
return sum;
} int main() { int a[]={ 2, 3, 4 ,5, -7, 8 ,-4 ,-3, 7 };
int low;
int high ;
int sum=finf_maximux_subaarray(a,low,high,9);
cout<<sum<<endl;
cout<<low<<'\t'<<high<<endl;
return 0;
}