題目:返回一個(gè)整數(shù)數(shù)組中最大子數(shù)組的和。

要求：

　　1、?輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。

　　2、 數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。

　　3、 求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)

?

設(shè)計(jì)思想：

　　核心算法：動(dòng)態(tài)規(guī)劃。

　　剛開始的時(shí)候并沒有找到合適的算法，只能夠設(shè)置數(shù)組的長度為特定的數(shù)值，然后每一種情況都考慮到，但是對(duì)于很大的數(shù)值來說，就無法實(shí)現(xiàn)了，直到找到了動(dòng)態(tài)規(guī)劃方法，然后才解決了核心的算法問題，時(shí)間復(fù)雜度為O（n）滿足題目需求。

?

源代碼：　

1 //數(shù)組1 2 //胡浩特、朱子嘉 2016/3/21 3 4 #include<iostream> 5 using namespace std; 6 7 int MaxSum3(int a[], int n){//優(yōu)化方案 時(shí)間O（n） 空間 O(1) 8 //int A，N; 9 int nStart = a[n - 1]; 10 int nAll = a[n - 1]; 11 for (int i = n - 2; i >= 0; i--) 12 { 13 if (nStart<0) 14 nStart = 0; 15 nStart += a[i]; 16 if (nStart>nAll) 17 nAll = nStart; 18 } 19 return nAll; 20 } 21 int main() 22 { 23 24 int i, length; 25 cout << "請(qǐng)輸入數(shù)組長度："; 26 cin >> length; 27 int a[50]; 28 cout << "請(qǐng)輸入數(shù)組值："; 29 30 for (i = 0; i < length; i++) 31 { 32 cin >> a[i]; 33 } 34 35 36 cout<<MaxSum3(a, length)<<endl; 37 return 0; 38 }

?

結(jié)果截圖：

　　三組測(cè)試數(shù)據(jù)：

　　1、都為正數(shù)，最大值為數(shù)組之和。

　　

　　2、都為負(fù)數(shù)，結(jié)果為最大的負(fù)數(shù)。

　　

　　3、有正數(shù)有負(fù)數(shù)還有有0。

　　

實(shí)驗(yàn)總結(jié)：

　　整個(gè)實(shí)驗(yàn)的關(guān)鍵在于算法的實(shí)現(xiàn)，對(duì)于這個(gè)問題來說有三種合適的算法，但是只有動(dòng)態(tài)規(guī)劃才滿足時(shí)間復(fù)雜度的要求。通過查找資料和自己研究才找到合適的算法。對(duì)于我來說，實(shí)驗(yàn)很簡(jiǎn)單但是還是花費(fèi)了不少的努力。這一次實(shí)驗(yàn)是一個(gè)新的開始，希望自己可以做好數(shù)組的一系列的實(shí)驗(yàn)。

轉(zhuǎn)載于:https://www.cnblogs.com/JYQ-hu/p/5313171.html

總結(jié)

以上是生活随笔為你收集整理的数组01的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。