#include?
#include
#include?
using?namespace?std;

/*?o（n^3）?的下標窮舉方法?*/
int?getMaxSum1（int?iarray[]?int?n）
{
int?maxSum?=?0;
for?（int?i?=?0;?i?{
???for?（int?j?=?i;?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?{
???int?tmp?=?0;
???for?（int?j?=?i;?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?{
???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?<