Problem#
給你一個陣列 nums，你要挑兩個 index i 和 j ，回傳 (nums[i]-1) * (nums[j]-1) 的最大值。
測資限制#
- $2 \le n \le 500$
- $1 \le val \le 10^3$
想法#
naive: 暴力 $O(n^2)$ 去掃
觀察：題目要求最大值，而最大值通常是最大和次大的數字組成，只要找到這兩個數字，算出 (nums[i]-1) * (nums[j]-1) 即可。找到數字: 可以 sort $O(n\log{n})$ 後 $O(1)$ 找到；或是紀錄最大和次大，掃一次 $O(n)$
AC Code#
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(1)$