最大子段和/三种方法/c++

最大子段和/三种方法/c++语言/(内有报告) 蛮力法，动态规划法，分治法。 可比较时间，随机输入数据......

#include 
#include
#include 
using namespace std;

/* o（n^3） 的下标穷举方法 */
int getMaxSum1（int iarray[] int n）
{
int maxSum = 0;
for （int i = 0; i < n; ++i）
{
   for （int j = i; j < n; ++j）
   {
    int tmp = 0;
    for （int k = i; k <=j; ++k）
    {
     tmp += iarray[k];
    }
    if （ tmp > maxSum ）
    {
     maxSum = tmp;
     //此处还可以记录下取得最大值的下标i和j，本程序省略了
    }
   }
}

return maxSum;
}

/* o（n^2） 的下标穷举方法 */
int getMaxSum2（int iarray[] int n）
{
int maxSum = 0;
for （int i = 0; i < n; ++i）
{
   int tmp = 0;
   for （int j = i; j < n; ++j）
   {
    tmp += iarray[j];
    if （ tmp > maxSum ）
    {
     maxSum = tmp;
     //此处可以记录下取得最大值的下标i和j，本程序忽略了
    }
   }
}

return maxSum;
}

/* o（nlogn）得分治递归方法 */
/* 说明: 分治的思想是原长为n的序列的子段和的最大值可能出现在左边n/2的子段里，也可能
只出现在右边n/2的字段里，也可能左边子段一部分，右边子段一部分。这样，递归的算出3个值:
左边n/2的最大字段和，右边n/2的最大子段和，包括2部分的最大子段和，然后取其中最大的最为
整个序列的最大子段和。递归的结束条件是当序列只有1个元素，2个元素时直接找出最大子段和，
递归结束。
时间复杂性分析: f（n） = 2*f（n/2） + o（n/2） 最后为o（nlogn）。
*/

int getMaxSum3（int iarray[] int startIndex int endIndex）
{
if （ endIndex == startIndex ） //只有一个元素
{
   return iarray[startIndex];
}

if （ endIndex - startIndex == 1 ）
{
   int tmp = iarray[startIndex] + iarray[endIndex];
   tmp = tmp > iarray[startIndex] ? tmp : iarray[startIndex];
   tmp = tmp > iarray[endIndex] ? tmp : iarray[endIndex];
   return tmp;
}

int leftMaxSum = getMaxSum3（iarray startIndex （startIndex + endIndex）/2）; //左边一半序列的最大子段和
int rightMaxSum = getMaxSum3（iarray （startIndex + endIndex）/2+1 endIndex）;//右边一半序列的最大子段和

int s1 = 0;
int s2 = 0;
int tmp = 0;

for （int i = （startIndex + endIndex）/2; i >= startIndex; --i）
{
   tmp = tmp + iarray[i];
   if （ tmp > s1 ）
   {
    s1 = tmp;
   }
}

tmp = 0;
for （ i = （startIndex + endIndex）/2+1; i <= endIndex; ++i）
{
   tmp = tmp + iarray[i];
   if （ tmp > s2 ）
   {
    s2 = tmp;
   }
}
int middleMaxSum = s1 + s2;
int maxSum = leftMaxSum > rightMaxSum ? leftMaxSum : rightMaxSum;
maxSum = maxSum > middleMaxSum ? maxSum : middleMaxSum;

return maxSum;
}

/* o（n）的动态规划方法 */
int getMaxSum4（int iarray[] int n）
{
int maxSum = 0;
int b = 0;
for （int i = 0; i < n; ++i）
{
   if （ b > 0 ）
   {
    b = b + iarray[i];
   }
   else
   {
    b = iarray[i];
   }
   if （ b > maxSum ）
   {
    maxSum = b;
   }
}

return maxSum;
}

int main（）
{int nicho;
clock_t t1t2t3t4t5t6;
cout<<“---------------计算1班 唐锦恒 43----------------\n“;
cout<cout<<“手动输入，请按1，随机输入请按2\n“;
cin>>cho;
cout<<“请输入序列的长度“<cin>>n;
int *iarray=new int[n];
if（cho==2） 
{srand（ （unsigned）time（ NULL ） ）;
//cout<<“其序列为：“<for（i=1;i<=n;i++）
{iarray[i]=（rand（）/13-1129）;  
//cout<<“  “<}}
else {cout<<“请输入序列“<for（i=0;icin>>iarray[i];}
//int iarray[10] = {2 -5 8 7 -6 -3 10 12 2 1};
t1=clock（）;
int maxSum1 = getMaxSum1（iarray n）;
t2=clock（）;
cout<cout << “蛮力法最大子段和为: “ << ma

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3832  2009-11-27 22:18  最大子段和..cpp

     文件      93184  2009-11-13 21:17  最大子段和.doc

----------- ---------  ---------- -----  ----

                97016                    2