不才小鲁弟提供个自己的算法:
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)，
: 所以是否多练习这类问题可以增进自己的逻辑思考能力? 对工作能力也会有帮助~