按難度排序，找了一道最水的題先來做做，題目鏈接：http://www.nowcoder.com/practice/1f7675ae7a9e40e4bd04eb754b62fd00?tpId=49&tqId=29281&rp=6&ru=/ta/2016test&qru=/ta/2016test/question-ranking??

最大差值

• 熱度指數：4410時間限制：3秒空間限制：32768K
• 本題知識點：?貪心
• ?算法知識視頻講解

題目描述

有一個長為n的數組A，求滿足0≤a≤b<n的A[b]-A[a]的最大值。

給定數組A及它的大小n，請返回最大差值。

測試樣例： [10,5],2 返回：0 比較簡單的動態規劃題，用了兩種方法過的（也不能說兩種方法，只不過后一種方法復雜度比較低~）。方法一就是用雙層循環遍歷，方法二的復雜度比較低，用了一個循環就解決了，在循環內同時做兩件事情，一個是更新最小值，一個是更新最小差值。

方法1：

int getDis(vector<int> A, int n) {//時間復雜度O(n^2) 空間復雜度O(1)int maxn=0;for(int i=0;i<n-1;i++){for(int j=i+1;j<n;j++){maxn=max(maxn,(A[j]-A[i]));}}return maxn; }方法2：

int getDis(vector<int> A, int n) {//時間復雜度O(n) 空間復雜度O(1)// write code hereint maxDiff=0;//初始化最大差值int minNum=A[0];//初始化最小值for(int i=1;i<n;++i){//遍歷if(A[i]<minNum)minNum=A[i];//更新最小值if(A[i]-minNum>maxDiff)maxDiff=A[i]-minNum;//更新最大差值}return maxDiff; }
每天一道題，保持新鮮感，就這樣~

總結

以上是生活随笔為你收集整理的【牛客网】马三来刷题之最大差值的全部內容，希望文章能夠幫你解決所遇到的問題。

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