- 相關(guān)推薦
程序員精選面試題100題
題目：在數(shù)組中，數(shù)字減去它右邊的數(shù)字得到一個數(shù)對之差。求所有數(shù)對之差的最大值。例如在數(shù)組{2, 4, 1, 16, 7, 5, 11, 9}中，數(shù)對之差的最大值是11，是16減去5的結(jié)果。
分析：看到這個題目，很多人的第一反應(yīng)是找到這個數(shù)組的最大值和最小值，然后覺得最大值減去最小值就是最終的結(jié)果。這種思路忽略了題目中很重要的一點：數(shù)對之差是一個數(shù)字減去它右邊的數(shù)字。由于我們無法保證最大值一定位于數(shù)組的左邊，因此這個思路不管用。
于是我們接下來可以想到讓每一個數(shù)字逐個減去它右邊的所有數(shù)字，并通過比較得到數(shù)對之差的最大值。由于每個數(shù)字需要和它后面的O(n)個數(shù)字作減法，因此總的時間復雜度是O(n2)。
解法一：分治法
通常蠻力法不會是最好的解法，我們想辦法減少減法的次數(shù)。假設(shè)我們把數(shù)組分成兩個子數(shù)組，我們其實沒有必要拿左邊的子數(shù)組中較小的數(shù)字去和右邊的子數(shù)組中較大的數(shù)字作減法。我們可以想象，數(shù)對之差的最大值只有可能是下面三種情況之一：(1)被減數(shù)和減數(shù)都在第一個子數(shù)組中，即第一個子數(shù)組中的數(shù)對之差的最大值;(2)被減數(shù)和減數(shù)都在第二個子數(shù)組中，即第二個子數(shù)組中數(shù)對之差的最大值;(3)被減數(shù)在第一個子數(shù)組中，是第一個子數(shù)組的最大值。減數(shù)在第二個子數(shù)組中，是第二個子數(shù)組的最小值。這三個差值的最大者就是整個數(shù)組中數(shù)對之差的最大值。
在前面提到的三種情況中，得到第一個子數(shù)組的最大值和第二子數(shù)組的最小值不是一件難事，但如何得到兩個子數(shù)組中的數(shù)對之差的最大值?這其實是原始問題的子問題，我們可以遞歸地解決。下面是這種思路的參考代碼：
int MaxDiff_Solution1(int numbers[], unsigned length)
{
if(numbers == NULL || length < 2)
return 0;
int max, min;
return MaxDiffCore(numbers, numbers + length - 1, &max, &min);
}
int MaxDiffCore(int* start, int* end, int* max, int* min)
{
if(end == start)
{
*max = *min = *start;
return 0x80000000;
}
int* middle = start + (end - start) / 2;
int maxLeft, minLeft;
int leftDiff = MaxDiffCore(start, middle, &maxLeft, &minLeft);
int maxRight, minRight;
int rightDiff = MaxDiffCore(middle + 1, end, &maxRight, &minRight);
int crossDiff = maxLeft - minRight;
*max = (maxLeft > maxRight) ? maxLeft : maxRight;
*min = (minLeft < minRight) ? minLeft : minRight;
int maxDiff = (leftDiff > rightDiff) ? leftDiff : rightDiff;
maxDiff = (maxDiff > crossDiff) ? maxDiff : crossDiff;
return maxDiff;
}
在函數(shù)MaxDiffCore中，我們先得到第一個子數(shù)組中的最大的數(shù)對之差leftDiff，再得到第二個子數(shù)組中的最大數(shù)對之差rightDiff。接下來用第一個子數(shù)組的最大值減去第二個子數(shù)組的最小值得到crossDiff。這三者的最大值就是整個數(shù)組的最大數(shù)對之差。
解法二：轉(zhuǎn)化成求解子數(shù)組的最大和問題
接下來再介紹一種比較巧妙的解法。如果輸入一個長度為n的數(shù)組numbers，我們先構(gòu)建一個長度為n-1的輔助數(shù)組diff，并且diff[i]等于numbers[i]-numbers[i+1](0<=i)。如果我們從數(shù)組diff中的第i個數(shù)字一直累加到第j個數(shù)字(j > i)，也就是diff[i] + diff[i+1] + … + diff[j] = (numbers[i]-numbers[i+1]) + (numbers[i + 1]-numbers[i+2]) + ... +(numbers[j] numbers[j+ 1]) = numbers[i] numbers[j + 1]。
分析到這里，我們發(fā)現(xiàn)原始數(shù)組中最大的數(shù)對之差(即numbers[i] numbers[j + 1])其實是輔助數(shù)組diff中最大的連續(xù)子數(shù)組之和。我們在本系列的博客的第3篇《求子數(shù)組的最大和》中已經(jīng)詳細討論過這個問題的解決方法。基于這個思路，我們可以寫出如下代碼：
int MaxDiff_Solution2(int numbers[], unsigned length)
{
if(numbers == NULL || length < 2)
return 0;
int* diff = new int[length - 1];
for(int i = 1; i < length; ++i)
diff[i - 1] = numbers[i - 1] - numbers[i];
int currentSum = 0;
int greatestSum = 0x80000000;
for(int i = 0; i < length - 1; ++i)
{
if(currentSum <= 0)
currentSum = diff[i];
else
currentSum += diff[i];
if(currentSum > greatestSum)
greatestSum = currentSum;
}
[] diff;
return greatestSum;
}
解法三：動態(tài)規(guī)劃法
既然我們可以把求最大的數(shù)對之差轉(zhuǎn)換成求子數(shù)組的最大和，而子數(shù)組的最大和可以通過動態(tài)規(guī)劃求解，那我們是不是可以通過動態(tài)規(guī)劃直接求解呢?下面我們試著用動態(tài)規(guī)劃法直接求數(shù)對之差的最大值。
我們定義diff[i]是以數(shù)組中第i個數(shù)字為減數(shù)的所有數(shù)對之差的最大值。也就是說對于任意h(h < i)，diff[i]≥number[h]-number[i]。diff[i](0≤i)的最大值就是整個數(shù)組最大的數(shù)對之差。
假設(shè)我們已經(jīng)求得了diff[i]，我們該怎么求得diff[i+1]呢?對于diff[i]，肯定存在一個h(h < i)，滿足number[h]減去number[i]之差是最大的，也就是number[h]應(yīng)該是number[i]之前的所有數(shù)字的最大值。當我們求diff[i+1]的時候，我們需要找到第i+1個數(shù)字之前的最大值。第i+1個數(shù)字之前的最大值有兩種可能：這個最大值可能是第i個數(shù)字之前的最大值，也有可能這個最大值就是第i個數(shù)字。第i+1個數(shù)字之前的最大值肯定是這兩者的較大者。我們只要拿第i+1個數(shù)字之前的最大值減去number[i+1]，就得到了diff[i+1]。
int MaxDiff_Solution3(int numbers[], unsigned length)
{
if(numbers == NULL || length < 2)
return 0;
int max = numbers[0];
int maxDiff = max - numbers[1];
for(int i = 2; i < length; ++i)
{
if(numbers[i - 1] > max)
max = numbers[i - 1];
int currentDiff = max - numbers[i];
if(currentDiff > maxDiff)
maxDiff = currentDiff;
}
return maxDiff;
}
在上述代碼中，max表示第i個數(shù)字之前的最大值，而currentDiff表示diff[i] (0≤i)，diff[i]的最大值就是代碼中maxDiff。
解法小結(jié)
上述三種代碼，雖然思路各不相同，但時間復雜度都是O(n)(第一種解法的時間復雜度可以用遞歸公式表示為T(n)=2(n/2)+O(1)，所以總體時間復雜度是O(n))。我們也可以注意到第一種方法是基于遞歸實現(xiàn)，而遞歸調(diào)用是有額外的時間、空間消耗的(比如在調(diào)用棧上分配空間保存參數(shù)、臨時變量等)。第二種方法需要一個長度為n-1的輔助數(shù)組，因此其空間復雜度是O(n)。第三種方法則沒有額外的時間、空間開銷，并且它的代碼是最簡潔的，因此這是最值得推薦的一種解法。
【程序員面試題100題】相關(guān)文章：
2014年MBA面試題目大綱100題07-11
程序員面試題精選07-12
入門級PHP程序員面試題07-09
c面試題08-04
華為面試題07-11
「MySQL」經(jīng)典面試題07-11
面試題與技巧07-12
采購面試題07-11