我覺得有些人都陷入了一個盲點,
求最大整數值,該值不一定為0或正整數的,其實也有可能為負整數。
我的解法,基本概念很簡單,可以再優化,沒有針對陣列長度0以下除錯,
但是我懶…
語言用C#,時間複雜度O(n)或O(n-1),根本沒差Orz
基本概念是
1. 一次迴圈跑完
2. 同時計算兩種相鄰的數字,然後再比較
目前可以優化的地方有
1. 針對陣列長度0以下除錯
2. 部分判斷流程可以再更好,加速計算時間
不考慮分割陣列與其他演算法是因為
1. 可讀性。如果程式接手,希望第一眼就知道在做什麼
2. 目前效率可接受。等哪天陣列長度是一百萬,應該就要換演算法了
private void button1_Click(object sender, EventArgs e)
{
int[] array1 = { 2, -7, 0, 2, 3, 8, -6, 5 };
int[] array2 = { -2, 0, 3, 5, -7 };
int max1 = this.CalculateMax(array1);
int max2 = this.CalculateMax(array2);
Console.WriteLine(max1); // 48
Console.WriteLine(max2); // 15
}
private int CalculateMax(int[] array)
{
if (array.Length == 1) // 陣列長度1,回傳該值
{
return array[0];
}
int max = array[0] * array[1]; // 初始max
for (int i = 0; i < array.Length - 1; i++)
{
// 計算相鄰兩個數字
int maxAdjacent2 = array[i] * array[i + 1];
// 計算相鄰三個數字,初始化
int maxAdjacent3 = maxAdjacent2 - 1;
if (i <= array.Length - 3)
{
maxAdjacent3 = array[i] * array[i + 1] * array[i + 2];
}
// 計算最大結果
if (maxAdjacent2 >= maxAdjacent3 && maxAdjacent2 > max)
{
max = maxAdjacent2;
}
else if (maxAdjacent3 >= maxAdjacent2 && maxAdjacent3 > max)
{
max = maxAdjacent3;
}
}
return max;
}
邏輯上應該沒什麼問題,
有錯誤麻煩請指出,謝謝。
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.249.117.38
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404444170.A.84E.html
※ 編輯: StupidGaGa (60.249.117.38), 07/04/2014 11:39:10