※ 引述《sleeper0121 (sleeper)》之銘言：
: 今天去面試，裡面有題題目是這樣:
: 寫個函式，傳個整數陣列進去，陣列裡面的整數可以是正數、負數或 0
: 請回傳一個陣列裡面相鄰互乘的最大整數值
: 例如: [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5]
: 就是 2 * 3 * 8 = 48
: 再一個例子: [-2 , 0 , 3 , 5 , -7]
: 就是 3 * 5 = 15
: 請問這題思考邏輯大概是怎樣呢?
: 當下沒解出來，害我回家後還一直再想 XD
int MaxSubArrayProduct(int A[], int n)
{
int curSubarrMax = 1;
int dpMax = INT_MIN;
for (int i = 0; i < n; ++i)
{
curSubarrMax = std::max(curSubarrMax * A[i], A[i]);
dpMax = std::max(dpMax, curSubarrMax);
}
return dpMax;
}
Complexity:
O(n) time
O(1) space