总结一下目前的几种算法：
1：暴力求解：直接组合求解
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];
}
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;
}
{
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;
}
int low;
int high ;
int sum=finf_maximux_subaarray(a,low,high,9);
cout<<sum<<endl;
cout<<low<<'t'<<high<<endl;
return 0;
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
