[問題背景]

已知某個商品一段時間的價格，求在某一天買進(jìn)，然后在之后的某一天賣出，求最大利益。

?

[問題分析]（著急看算法的小盆友請直接跳過這一節(jié)）

不難發(fā)現(xiàn)，有個很特殊的情況，如果價格一直在漲，顯然第一天買進(jìn)，最后一天賣出能夠獲得最大利益。所以，當(dāng)價格有漲有跌的時候，這個問題才有意義。

首先，最容易的想法是暴力搜索。我們可以枚舉買進(jìn)和賣出的日期，然后計算對應(yīng)的獲利，最后得到一個最大利益。這種方式的時間復(fù)雜度是O(n^2)的，如下（c代碼）：

1 #include <stdio.h> 2 #define MaxN 120 3 #define INF 0x3f 4 int main() 5 { 6 int a[MaxN], n; 7 int i, j; 8 int Ans, Delta, st = 0, ed = 0; 9 scanf("%d", &n); 10 for(i = 1; i <= n; i++) 11 scanf("%d", &a[i]); 12 /*暴力枚舉買入日期和賣出日期，然后計算其中的獲利*/ 13 Ans = -INF; 14 for(i = 1; i < n; i++) //顯然不能在最后一天買入 15 for(j = i + 1; j <= n; j++) //至少在后一天賣出 16 { 17 Delta = a[j] - a[i]; 18 if(Ans < Delta) 19 { 20 Ans = Delta; 21 st = i; 22 ed = j; 23 } 24 } 25 printf("獲利：%d元\n在第%d天買入，在第%d天賣出\n", Ans, st, ed); 26 return 0; 27 } View Code

?

然后，我們覺得這種方法的時間復(fù)雜度太高了，于是思考更優(yōu)的方法。

有一種嘗試，將原來的保存每天的價格的數(shù)組改變一下，變成保存當(dāng)前價格相對于前一天的變化。為了敘述方便，我們將先前的保存每天的價格的數(shù)組記為a[]，其中a[i]表示第i天的商品價格是多少；將記錄價格變化（價格差）的新的數(shù)組記為b[]，其中b[i]表示第i天的價格相比于第i-1天漲了多少（負(fù)數(shù)表示降價），也可以理解為b[i]保存的是“如果第i-1天買進(jìn)第i天賣出所得利益”。于是，我們發(fā)現(xiàn)，第i天買進(jìn)然后第j天賣出，可以分解為：第i天買進(jìn)、第i+1天賣出、第i+1天買進(jìn)、第i+2天賣出……第j-1天買進(jìn)、第j天賣出。

咋一看覺得把復(fù)雜度提高了，因為原本求“第i天買進(jìn)，第j天賣出”所得利益只需要O(1)的復(fù)雜度就可以搞定了，現(xiàn)在還需要做一次累加，變成了O(n)級別的操作了。各位看官先別著急，咱們先分析一下問題轉(zhuǎn)換成了什么，再分析復(fù)雜度不遲。

對a[]的問題是，求兩個位置i和j，其中i<j，使得a[j]-a[j]最大；對b[]的問題是，求兩個位置i和j，使得a[i]+a[i+1]+……+a[j]最大（這個和式也就是所得利益）。也就是說，現(xiàn)在的問題變成了求連續(xù)子數(shù)組最大和。我們?nèi)匀粡谋┝λ阉鏖_始思考，一個很樸素的想法是，枚舉買進(jìn)的日期，然后計算在之后的每一天賣出所能獲得的利益。最后我們同樣可以獲得最大利益，時間復(fù)雜度仍然是O(n^2)，如下（c代碼）：

1 #include <stdio.h> 2 #define MaxN 120 3 #define INF 0x3f 4 int main() 5 { 6 int a[MaxN], n; 7 int i, j; 8 int Ans, Sum, st = 0, ed = 0; 9 scanf("%d", &n); 10 a[0] = 0; 11 for(i = 1; i <= n; i++) 12 scanf("%d", &a[i]); 13 for(i = n; i >= 1; i--) 14 a[i] -= a[i - 1]; //這里的a[]就是指的新得到的b[] 15 /*暴力枚舉買入日期*/ 16 Ans = -INF; 17 for(i = 1; i < n; i++) //顯然不能在最后一天買入 18 { 19 Sum = 0; 20 for(j = i + 1; j <= n; j++) //至少在后一天賣出 21 { 22 Sum += a[j]; 23 if(Ans < Sum) 24 { 25 Ans = Sum; 26 st = i; 27 ed = j; 28 } 29 } 30 } 31 printf("獲利：%d元\n在第%d天買入，在第%d天賣出\n", Ans, st, ed); 32 return 0; 33 } View Code

?

現(xiàn)在估計有看官覺得zyy又在裝神弄鬼了…… 明明還是O(n^2)的好嗎！還弄這么復(fù)雜很好玩嗎啊摔！w(ﾟДﾟ)w

……摸摸，都說了別著急…… 下面上干貨。

我們來分析一下對于數(shù)組b[]來說，答案會出現(xiàn)在什么地方。如果對數(shù)組b[]一分為二，那么最后求得的答案只能是三種情況：要么是全在左邊的連續(xù)子數(shù)組，要么是全在右邊的連續(xù)子數(shù)組，要么是橫跨中點的連續(xù)子數(shù)組。說到這里就應(yīng)該有一種靈光一現(xiàn)的感覺了吧~ 是的，這是一種基于分治思想的算法（你覺得是二分，或者是線段樹，甚至樹狀數(shù)組那都沒問題，不過我們這里說的是算法的思想），下面給出算法的具體實現(xiàn)。

?

[算法描述及實現(xiàn)]

對于一個數(shù)組，求下標(biāo)范圍為[left,right]的連續(xù)子數(shù)組最大和。將數(shù)組一分為二，記mid=(left+right)/2（具體實現(xiàn)個人更傾向于mid=left+(right-left)/2的寫法，這里不作解釋），那么最優(yōu)解要么是從[left,mid]得到，要么是從[mid+1,right]得到，要么是橫跨中點的一個答案。對于前兩種情況，是將問題完全轉(zhuǎn)化為一個規(guī)模更小的、本質(zhì)不變的子問題，遞歸進(jìn)去實現(xiàn)就可以了，這里我們需要解決的是如何求橫跨中點的情況。我們很容易發(fā)現(xiàn)，想要mid左右兩邊選出來的連續(xù)的數(shù)之和達(dá)到最大，讓左右兩邊分別達(dá)到最大即可。于是第三種情況：最大和=mid向左側(cè)延伸的最大和+mid向右側(cè)延伸的最大和。這個在同一級別的區(qū)間并起來看時間復(fù)雜度是O(n)的，二分的復(fù)雜度是O(lg n)的，所以總的復(fù)雜度是O(n lg n)。

下面是實現(xiàn)（c++代碼）：

1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 #define MaxN 120 5 #define INF 0x3f 6 int Get_Max_Sum(int *a, int L, int R, int &st, int &ed) 7 { 8 int Ret, tmp, mid = L + (R - L) / 2; 9 int s, e; 10 int Max1, Max2; 11 int i; 12 /*單個點的情況，直接返回*/ 13 if(L == R) 14 { 15 Ret = a[L]; 16 st = ed = L; 17 return Ret; 18 } 19 /*從左側(cè)得到答案*/ 20 Ret = Get_Max_Sum(a, L, mid, s, e); 21 st = s; ed = e; 22 /*從右側(cè)得到答案*/ 23 tmp = Get_Max_Sum(a, mid + 1, R, s, e); 24 if(Ret < tmp) 25 { 26 Ret = tmp; 27 st = s; ed = e; 28 } 29 /*橫跨mid的情況，實際上是指至少包括a[mid]和a[mid+1]*/ 30 //左側(cè) 31 s = mid; 32 tmp = 0; 33 Max1 = a[mid]; 34 for(i = mid; i >= L; i--) 35 { 36 tmp += a[i]; 37 if(tmp > Max1) 38 { 39 Max1 = tmp; 40 s = i; 41 } 42 } 43 //右側(cè) 44 e = mid + 1; 45 tmp = 0; 46 Max2 = a[mid + 1]; 47 for(i = mid + 1; i <= R; i++) 48 { 49 tmp += a[i]; 50 if(tmp > Max2) 51 { 52 Max2 = tmp; 53 e = i; 54 } 55 } 56 tmp = Max1 + Max2; 57 if(tmp > Ret) 58 { 59 Ret = tmp; 60 st = s; ed = e; 61 } 62 return Ret; 63 } 64 int main() 65 { 66 int a[MaxN], n; 67 int i; 68 int Ans, st = 0, ed = 0; 69 scanf("%d", &n); 70 for(i = 1; i <= n; i++) 71 scanf("%d", &a[i]); 72 for(i = n; i >= 2; i--) 73 a[i] -= a[i - 1]; //這里的a[]就是指的新得到的b[] 74 Ans = Get_Max_Sum(a, 2, n, st, ed); 75 printf("獲利：%d元\n在第%d天買入，在第%d天賣出\n", Ans, st - 1, ed); 76 return 0; 77 } View Code

?

解釋一下，這里寫的是c++的代碼，因為c語言中不包括變參，函數(shù)返回值處理略麻煩。

目前三個代碼沒有經(jīng)過對拍，最后一種方式當(dāng)然是正確的，但不保證我寫得沒有錯誤……挖個坑吧~

轉(zhuǎn)載于:https://www.cnblogs.com/CQBZOIer-zyy/p/5275917.html

總結(jié)

以上是生活随笔為你收集整理的[算法]一次商品交易利益最大化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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