行列或對角線最大的產品

Question

我最近碰到這個面試問題，Matrix largest product of n numbers in a row

我明白了滾動倍增的方法。我想知道是否會有進一步的優化，如果我將問題限定爲強制選擇整個行，列或對角線。

所以基本上現在的問題是， 給定一個NxM矩陣，找出具有最大乘積的行或列或對角線。

是否可以使用O（log n）算法？

Answer 1

你必須在每一行和每一列至少一次的樣子，所以你不能比O（max（M，N））做得更好。爲了簡單起見，許多人認爲M == N並將其表示爲O（N）。因爲您還需要查看行/列中的每個元素，這使得它成爲O（M * N）。基本上，這表明你需要在到達結果之前查看矩陣的每個元素。

Answer 2

NO，如果你矩陣N X M在最壞的情況下，你不能做任何比O(NM)更好，因爲你必須要找到所有行的產品，以及diagonals.You列不能避免這些計算。

你可以做小的優化等方法去除行/列/對角線那裏有零（因爲乘法會導致零）