不才小魯弟提供個自己的演算法:
1. 把整個陣列先分成很多sub_array 讓每個sub_array只有非零整數
2. 找出每個sub_array的最大值, 並比較之
3. 拿最大值跟0比(主要是看有沒有零, 如果沒有, 陣列間的最大值就是答案)
接著實作如何找出每個sub_array的最大值:
我的想法很簡單, 這邊是利用數字的特性, 因為都是整數(正整數或負整數或0)
越多數字乘在一起, 其絕對值越大, 所以我們只要去頭或去尾, 所得到第一個正數,
並比較左右誰大就是答案
假設某個sub_array有 a1, a2, a3, ... , an
先計算 mul = a1*a2*a3*...*an
接著每次去掉左右各一個數字得到left_mul(a1*...*an-1), 與right_mul(a2*...*an)
e.x.
如果
mul > 0 就return mul
否則:
(*)
left_mul = mul / an;
right_mul = mul / a1;
如果left_mul 是正數且大於right_mul 就回傳left_mul
如果right_mul是正數且大於left_mul 就回傳right_mul
如果兩個都是負數, 就跳到 (*) 再來一次
直到有人為正(或兩者都是)為止
附上C++ code
不過我boundary condition check 的很隨興XD,
可能弄一些其他輸入可以把我的程式搞爆
假設輸入是N
我的作法只有乘在一起要N-1次相乘 其他只要不用N次就可以找出答案
所以確定可以在3N的步數以內得到解答(應該不用, 我估最差的情況).
#include <iostream>
#include <cstdlib>
#define SIZE 20
using namespace std;
int find_sub_max( int arr_in[], int size );
int main()
{
int array_num[SIZE] = { -1,-2,-3, 0, 2, 4, 7, -1, 0, 8,
0, 29, 17, -2, -4, 2, 3, 0, 29, 7};
int count;
int sub_array_count;
int sub_array_size[SIZE] = {0};
int sub_array[SIZE][SIZE] = {0};
sub_array_count = 0;
count = 0;
int max;
for ( int i = 0; i < SIZE; i++ )
{
if ( array_num[i] != 0 )
{
sub_array[sub_array_count][count++] = array_num[i];
sub_array_size[sub_array_count]++;
} else {
max = 0;
if ( i != SIZE - 1)
{
sub_array_count++;
count = 0;
}
}
}
// check if there is any zero
int temp_max;
for ( int i = 0; i <= sub_array_count; i++ )
{
temp_max = find_sub_max(sub_array[i], sub_array_size[i]);
if ( max < temp_max )
{
max = temp_max;
}
}
cout << "the max value = " << max << endl;
cin.get();
}
int find_sub_max( int arr_in[], int size )
{
int left_max;
int right_max;
int result;
int mul;
mul = 1;
for ( int i = 0; i < size; i++ )
{
mul = mul * arr_in[i];
}
result = mul;
if ( result < 0 )
{
left_max = mul;
right_max = mul;
for (int i = 0; i < size; i++ )
{
if ( left_max > 0 )
{
if ( left_max > right_max )
{
return left_max;
} else
return right_max;
} else if ( right_max > 0 ) {
return right_max;
} else {
left_max = left_max / arr_in[size-i-1];
right_max = right_max / arr_in[i];
}
}
}
return result;
}
※ 引述《sleeper0121 (sleeper)》之銘言：
: 我是原 PO
: 沒想到這題可以引出這麼多篇 @@
: 小弟是個魯蛇，當下花了大概30分鐘沒想出來，
: 回去google幾個關鍵字也沒找到題目，
: 就上來Po版看看有沒有高手一下就解出來了 XD
: 順便看看解法~
: 當下題目就真的長這樣，有些定義的地方可能還是要問面試官會比較清楚，
: 不過我當時被要手寫的程式碼弄得很煩躁，解不出來就算了 = =
: 最後想請問一下，我對類似這種像ACM的題目一直都很沒轍....
: 不過開始工作後發現遇到這種問題的機會反而不多(我寫ASP.NET)，
: 所以是否多練習這類問題可以增進自己的邏輯思考能力? 對工作能力也會有幫助~