题目&＃xff1a;
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array
[2,3,-2,4],
the contiguous subarray[2,3]has the largest product &＃61;6.
题意&＃xff1a;
题目中给出一个&＃xff08;至少包含一个元素&＃xff09;整形数组&＃xff0c;求一个子数组&＃xff08;元素连续&＃xff09;&＃xff0c;使得其元素之积最大。
最直接了当的方法&＃xff0c;当然是暴力穷举&＃xff0c;但是其O(n^2)是无法通过LeetCode的OJ的。
以下给出了本题的解决方法&＃xff0c;O&＃xff08;n&＃xff09;时间复杂度&＃xff0c;C&＃43;&＃43;实现。
1 class Solution {
2 public:
3 int maxProduct(int A[], int n) {
4 int nMaxPro &＃61; A[0];
5 int max_tmp &＃61; A[0];
6 int min_tmp &＃61; A[0];
7
8 for(int i &＃61; 1; i
9 int a &＃61; A[i] * max_tmp;
10 int b &＃61; A[i] * min_tmp;
11
12 max_tmp &＃61; (( a > b ? a : b ) > A[i]) ? ( a > b ? a : b ) : A[i];
13 min_tmp &＃61; (( a a : b ) : A[i];
14
15 nMaxPro &＃61; (nMaxPro > max_tmp) ? nMaxPro : max_tmp;
16 }
17
18 return nMaxPro;
19 }
20 };
运行结果&＃xff1a;
希望各位看官不吝赐教&＃xff0c;小弟感谢~&＃xff01;
京公网安备 11010802041100号