程序员人生 网站导航

LeetCode-Maximum Product Subarray

栏目:php教程时间:2015-02-03 08:42:18

题目链接:点击打开链接

题目信息:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,⑵,4],
the contiguous subarray [2,3] has the largest product = 6.

解题思路: 习惯最小字符串的和,突然来了1道最小字符串的乘积,也挺成心思。

                  分两种情况讨论:字符数组中无0,有0。两种情况。

                 (1)字符数组中无0

                        字符数组中,其实就两种,偶数个负数,奇数个负数。

                       1,偶数个负数,例如 [ ⑴ 2 3 ⑷ 5],很明显最大的字符串就是全部。

                       2,奇数个负数,例如 [⑵ 2 5 ⑷ ⑶], 最大的字符串就是,第1个负数后面的子串[2 5 ⑷ ⑶].

                       所以综上所述,最大字符串就只有两种情况,1种是全部字符串,1种是第1个负数后面的字符串。所以只要存储这两种情况下的值,                        再进行比较就可以得出最后结果。

                   (2)字符串中有0

                        前面能实现,我们就把0后的数组,当做1个新的数组就可以实现了。例如[5 6 ⑸ 0 2 3 8 9 ⑸],就能够把0后面的数组看成新数组就行

                       [2 3 8 9 ⑸];

代码:

class Solution { public: int maxProduct(int A[], int n) { int preNum1 = 1; //Remember all the Numbers int preNum2 = 1; //Remember all the Behind Numbers of first negative bool start2; int answers ; if(n == 0) return 0; if(n > 0) answers = A[0]; int negSum = 0; for(size_t i = 0; i != n;i++) { preNum1 *= A[i]; //cout<<"preNum1="<<preNum1<<endl; answers = (preNum1 > answers? preNum1:answers); if(start2 == true) { preNum2 *= A[i]; //cout<<"preNum2="<<preNum2<<endl; answers = (preNum2 > answers? preNum2:answers); } if(A[i] < 0) { negSum ++; } if(negSum == 1 && start2 == false) { start2 = true; preNum2 = 1; } if(A[i] == 0) { answers = (answers > 0) ? answers : 0; preNum1 = 1; preNum2 = 1; negSum = 0; start2 = false; } } return answers; } };
转载请注明作者:vanish_dust

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐