Re: [討論] 面試遇到的考題

[csee (CSE)]

不才小魯弟提供個自己的演算法:

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)，
: 所以是否多練習這類問題可以增進自己的邏輯思考能力?  對工作能力也會有幫助~

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.136.220
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404470990.A.EC7.html
※ 編輯: csee (140.113.136.220), 07/04/2014 18:54:13