程序員精選面試題100題

題目：在數(shù)組中，數(shù)字減去它右邊的數(shù)字得到一個(gè)數(shù)對(duì)之差。求所有數(shù)對(duì)之差的最大值。例如在數(shù)組{2, 4, 1, 16, 7, 5, 11, 9}中，數(shù)對(duì)之差的最大值是11，是16減去5的結(jié)果。

分析：看到這個(gè)題目，很多人的第一反應(yīng)是找到這個(gè)數(shù)組的最大值和最小值，然后覺(jué)得最大值減去最小值就是最終的結(jié)果。這種思路忽略了題目中很重要的一點(diǎn)：數(shù)對(duì)之差是一個(gè)數(shù)字減去它右邊的數(shù)字。由于我們無(wú)法保證最大值一定位于數(shù)組的左邊，因此這個(gè)思路不管用。

于是我們接下來(lái)可以想到讓每一個(gè)數(shù)字逐個(gè)減去它右邊的所有數(shù)字，并通過(guò)比較得到數(shù)對(duì)之差的最大值。由于每個(gè)數(shù)字需要和它后面的O(n)個(gè)數(shù)字作減法，因此總的時(shí)間復(fù)雜度是O(n2)。

解法一：分治法

通常蠻力法不會(huì)是最好的解法，我們想辦法減少減法的次數(shù)。假設(shè)我們把數(shù)組分成兩個(gè)子數(shù)組，我們其實(shí)沒(méi)有必要拿左邊的子數(shù)組中較小的數(shù)字去和右邊的子數(shù)組中較大的數(shù)字作減法。我們可以想象，數(shù)對(duì)之差的最大值只有可能是下面三種情況之一：(1)被減數(shù)和減數(shù)都在第一個(gè)子數(shù)組中，即第一個(gè)子數(shù)組中的數(shù)對(duì)之差的最大值;(2)被減數(shù)和減數(shù)都在第二個(gè)子數(shù)組中，即第二個(gè)子數(shù)組中數(shù)對(duì)之差的最大值;(3)被減數(shù)在第一個(gè)子數(shù)組中，是第一個(gè)子數(shù)組的最大值。減數(shù)在第二個(gè)子數(shù)組中，是第二個(gè)子數(shù)組的最小值。這三個(gè)差值的最大者就是整個(gè)數(shù)組中數(shù)對(duì)之差的最大值。

在前面提到的三種情況中，得到第一個(gè)子數(shù)組的最大值和第二子數(shù)組的最小值不是一件難事，但如何得到兩個(gè)子數(shù)組中的數(shù)對(duì)之差的最大值?這其實(shí)是原始問(wèn)題的子問(wèn)題，我們可以遞歸地解決。下面是這種思路的參考代碼：

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中，我們先得到第一個(gè)子數(shù)組中的最大的數(shù)對(duì)之差leftDiff，再得到第二個(gè)子數(shù)組中的最大數(shù)對(duì)之差rightDiff。接下來(lái)用第一個(gè)子數(shù)組的最大值減去第二個(gè)子數(shù)組的最小值得到crossDiff。這三者的最大值就是整個(gè)數(shù)組的最大數(shù)對(duì)之差。

解法二：轉(zhuǎn)化成求解子數(shù)組的最大和問(wèn)題

接下來(lái)再介紹一種比較巧妙的解法。如果輸入一個(gè)長(zhǎng)度為n的數(shù)組numbers，我們先構(gòu)建一個(gè)長(zhǎng)度為n-1的輔助數(shù)組diff，并且diff[i]等于numbers[i]-numbers[i+1](0<=i)。如果我們從數(shù)組diff中的第i個(gè)數(shù)字一直累加到第j個(gè)數(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ù)對(duì)之差(即numbers[i] numbers[j + 1])其實(shí)是輔助數(shù)組diff中最大的連續(xù)子數(shù)組之和。我們?cè)诒鞠盗械牟┛偷牡?篇《求子數(shù)組的最大和》中已經(jīng)詳細(xì)討論過(guò)這個(gè)問(wèn)題的解決方法。基于這個(gè)思路，我們可以寫出如下代碼：

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;

}

解法三：動(dòng)態(tài)規(guī)劃法

既然我們可以把求最大的數(shù)對(duì)之差轉(zhuǎn)換成求子數(shù)組的最大和，而子數(shù)組的最大和可以通過(guò)動(dòng)態(tài)規(guī)劃求解，那我們是不是可以通過(guò)動(dòng)態(tài)規(guī)劃直接求解呢?下面我們?cè)囍�用�?dòng)態(tài)規(guī)劃法直接求數(shù)對(duì)之差的最大值。

我們定義diff[i]是以數(shù)組中第i個(gè)數(shù)字為減數(shù)的所有數(shù)對(duì)之差的最大值。也就是說(shuō)對(duì)于任意h(h < i)，diff[i]≥number[h]-number[i]。diff[i](0≤i)的最大值就是整個(gè)數(shù)組最大的數(shù)對(duì)之差。

假設(shè)我們已經(jīng)求得了diff[i]，我們?cè)撛趺辞蟮胐iff[i+1]呢?對(duì)于diff[i]，肯定存在一個(gè)h(h < i)，滿足number[h]減去number[i]之差是最大的，也就是number[h]應(yīng)該是number[i]之前的所有數(shù)字的最大值。當(dāng)我們求diff[i+1]的時(shí)候，我們需要找到第i+1個(gè)數(shù)字之前的最大值。第i+1個(gè)數(shù)字之前的最大值有兩種可能：這個(gè)最大值可能是第i個(gè)數(shù)字之前的最大值，也有可能這個(gè)最大值就是第i個(gè)數(shù)字。第i+1個(gè)數(shù)字之前的最大值肯定是這兩者的較大者。我們只要拿第i+1個(gè)數(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個(gè)數(shù)字之前的最大值，而currentDiff表示diff[i] (0≤i)，diff[i]的最大值就是代碼中maxDiff。

解法小結(jié)

上述三種代碼，雖然思路各不相同，但時(shí)間復(fù)雜度都是O(n)(第一種解法的時(shí)間復(fù)雜度可以用遞歸公式表示為T(n)=2(n/2)+O(1)，所以總體時(shí)間復(fù)雜度是O(n))。我們也可以注意到第一種方法是基于遞歸實(shí)現(xiàn)，而遞歸調(diào)用是有額外的時(shí)間、空間消耗的(比如在調(diào)用棧上分配空間保存參數(shù)、臨時(shí)變量等)。第二種方法需要一個(gè)長(zhǎng)度為n-1的輔助數(shù)組，因此其空間復(fù)雜度是O(n)。第三種方法則沒(méi)有額外的時(shí)間、空間開(kāi)銷，并且它的代碼是最簡(jiǎn)潔的，因此這是最值得推薦的一種解法。

【程序員面試題100題】相關(guān)文章：

2014年MBA面試題目大綱100題07-11

程序員面試題精選07-12

入門級(jí)PHP程序員面試題07-09

100個(gè)最權(quán)威的招聘面試題及回答解析07-11

誰(shuí)有近幾年華為和中興公司的Java程序員面試題07-11

c面試題08-04

華為面試題07-11

「MySQL」經(jīng)典面試題07-11

面試題與技巧07-12

采購(gòu)面試題07-11