求數組中最大子數組的和

一、程序要求

1、返回一個整數數組中最大子數組的和；

2、輸入一個整數數組，數組中有正數也有負數；

3、數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和；

4、求所有子數組的和的最大值，要求時間復雜度為O（n）；

二、程序設計思想

????數組的長度和各個元素由鍵盤鍵入。先將各元素累加，每加一個數，看結果是否為0，若為0，重置結果，并且結果與最大子數組和（簡稱最大和）比較，若有更大的和，就保存較大的結果到最大和中。若最大和與結果的值均為0，說明數組為負數數組，最大子數組即為最大元素。

三、源程序

//李俏、張瑩熒，2016.3.21 //求整數數組的最大子數組的和 #include<iostream> using namespace std;int main() {int arrlength,i;int j;int maxsum=0,sum=0;int arr[100];cout<<"請輸入數組長度：";cin>>arrlength;if(arr==NULL||arrlength==0){//exit(1);return 0;}cout<<"請輸入數組元素：";for(i=0;i<arrlength;i++){cin>>arr[i];}maxsum=0;sum=0;for(i=0;i<arrlength;i++){sum=sum+arr[i];//累加if(sum<0) //當前和小于0，重置為0 {sum=0;}if(sum>maxsum) // 當前和大于最大和，則重置最大和 {maxsum=sum;}}if(maxsum==0) //maxsum=0,說明數組中的數值均為負數 {maxsum=arr[0];for(i=1;i<arrlength;i++){if(arr[i]>maxsum)//求出負數數組的最大值 {maxsum=arr[i];}}}cout<<"最大子數組的和為："<<maxsum<<endl;return 0;//for(i=0;i<arrlength;i++)//{// sum=0;// for(j=0;j<arrlength;j++)// {// sum += arr[j];// if(sum<0) //當前和小于0，重置為0// {// sum=0;// }// if(sum>maxsum)// {// maxsum=sum;// }// }//}//cout<<"最大子數組的和為："<<maxsum<<endl;//return 0; }

?

四、結果截圖

五、項目計劃日志

周活動總結表??

姓名：李俏????????? 日期：2016年3月19日

日期?? 任務	聽課?	編寫程序	閱讀課本	準備考試	?	?	日總計
周日（3.20）	?	30	30	?	?	?	?60
周一	120	30	30	?	?	?	180
周二	?	30	30	?	?	?	60
周三	?	30	30	?	?	?	60
周四	120	?	30	?	?	?	150
周五	?	180	30	?	?	?	210
周六	?	60	30	?	?	?	120
周總結	240	360	210	?	?	?	810

?

?

?

?

?

?

?

?

?

?

?

?

?

六、時間記錄表：

學生：???李 俏?????????????????????????日期?：2016年3月12日?

教師：???王建民?????????????? ?????????課程?：軟件工程??????

日期	開始時間	結束時間	中斷時間	凈時間	活動	備注
?3.21	16:30	17:00	無	30	編寫程序?	作業?
?	20:10	20:40	無	30	閱讀	作業
?3.22	19:10	19:50	10	30	編寫程序	作業
?	20:00	20:30?	無	30	閱讀	?作業
?3.23	14:30	15:30	30min	30	編寫程序	?作業
?	20:00	20:30?	無	30	閱讀	?作業
3.24	18：50	19：20	無	30	編寫程序	作業
?	20：00	20：30	無	30	閱讀	?作業
?3.25	13:20	18:00	100?	180	編寫程序	?作業
?	21：10	21：40	無	30	閱讀	?作業
?3.26	12：00	?13：30	?30min	60	編寫程序	?作業

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

七、缺陷記錄日志：

學生????????李俏,張瑩熒????

日期 ? ??? 2016年3月25日? ?

教員????????? 王建民???????

程序號? ??2??

日期?	編號	類型	引入階段	排除階段	修復時間	修復缺陷
?3.24?	1	計算	設計	編譯	10min	?
	描述：?計算不出結果。
?3.24?	2	結果	編碼	編譯	5min	?
	描述：?沒有考慮純負數數組。
?3.24?	3	算法	編碼	查資料、問同學	30min	?
	描述：時間復雜度不符合要求。

?

?

?

?

?

?

?

?

?

?

?

八、工作照片?

小伙伴：張瑩熒（http://www.cnblogs.com/zhyying/）

轉載于:https://www.cnblogs.com/Aliqiao/p/5321866.html

總結

以上是生活随笔為你收集整理的结对项目——最大子数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。