※ 引述《sleeper0121 (sleeper)》之铭言：
: 今天去面试，里面有题题目是这样:
: 写个函式，传个整数阵列进去，阵列里面的整数可以是正数、负数或 0
: 请回传一个阵列里面相邻互乘的最大整数值
: 例如: [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5]
: 就是 2 * 3 * 8 = 48
: 再一个例子: [-2 , 0 , 3 , 5 , -7]
: 就是 3 * 5 = 15
: 请问这题思考逻辑大概是怎样呢?
: 当下没解出来，害我回家后还一直再想 XD
刚想一下写的，希望大家帮忙指教一下有没有逻辑上的瑕疵
function int ArrayMax(int[] arr)
{
// 宣告一个最后要回传的结果
int MaxValue = 0;
// 如果array长度只有1，就自己传回去
if(arr.length == 1)
return arr[0];
// 在下一个loop中纪录参数的arr中有没有出现任何一个0
bool hasZero = false;
// 开始scan arr中有没有0，遇到0递回送进前一段没有0的array.
//因为0ㄧ乘就变0
int startIndex = 0;
for(int i=0; i<arr.length; i++)
{
if(arr[i] == 0)
{
// 整个array有至少一个0，不用整个乘在一起
hasZero = true;
if(i > startIndex)
{
int temp = ArrayMax(subarray[startIndex ... (i-1)]);
if(MaxValue < temp)
MaxValue = temp;
startIndex = i + 1;
}
}
}
// 只要有任何一个0被找到，就表示分段都算完了，传回MaxValue
if(hasZero)
return MaxValue ;
// 否则，整个array都没有0. 再scanㄧ次找出几个负号
int NegativeCount = 0;
// FirstNegativeIndex 是第一个负号出现的位置
// LastNegativeIndex 是最后一个负号出现的位置
int FirstNegativeIndex = -1;
int LastNegativeIndex = -1;
for(int i=0; i<arr.length; i++)
{
if(arr[i] <0) // 发现负数
{
NegativeCount++;
if(FirstNegativeIndex == -1)
{
FirstNegativeIndex = i;
}
LastNegativeIndex = i;
}
}
// 若发现偶数个负号又没有0，整个相乘ㄧ定是正值，直接array每一个直接
// 相乘后传回结果
if(NegativeCount % 2 ==0)
{
return arr[0]*arr[1]*...*arr[length-1];
}
else
{
// 奇数个负号则找出第一个和最后一个，把这两个负号当切割点处理.
// 分别计算这两个负号切割出的四个array能找出的MAX是多少
return MAX(
ArrayMax(arr[LastNegativeIndex+1 ... length-1],
ArrayMax(arr[0 ... LastNegativeIndex-1],
ArrayMax(arr[FirstNegativeIndex+1 ... length-1],
ArrayMax(arr[0 ... FirstNegativeIndex-1]);
}
}