[leetCode][001] Maximum Product Subarray

题目:

  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 = 6.

题意:

  题目中给出一个(至少包含一个元素)整形数组,求一个子数组(元素连续),使得其元素之积最大。

  最直接了当的方法,当然是暴力穷举,但是其O(n^2)是无法通过LeetCode的OJ的。

  以下给出了本题的解决方法,O(n)时间复杂度,C++实现。

 class Solution {
public:
int maxProduct(int A[], int n) {
int nMaxPro = A[];
int max_tmp = A[];
int min_tmp = A[]; for(int i = ; i< n; ++i){
int a = A[i] * max_tmp;
int b = A[i] * min_tmp; max_tmp = (( a > b ? a : b ) > A[i]) ? ( a > b ? a : b ) : A[i];
min_tmp = (( a < b ? a : b ) < A[i]) ? ( a < b ? a : b ) : A[i]; nMaxPro = (nMaxPro > max_tmp) ? nMaxPro : max_tmp;
} return nMaxPro;
}
};

运行结果:

[leetCode][001] Maximum Product Subarray

希望各位看官不吝赐教,小弟感谢~!

上一篇:java:装饰模式,节点流和处理流


下一篇:转 基于Quick-cocos2dx 2.2.3 的动态更新实现完整篇。(打包,服务器接口,模块自更新