Create 152.乘积最大子数组(中等).md

JavaCodeMing · JavaCodeMing · commit e1c0ed6f09ca · 2020-06-29T08:32:00.000+08:00
diff --git a/Algorithm/152.乘积最大子数组(中等).md b/Algorithm/152.乘积最大子数组(中等).md
@@ -0,0 +1,43 @@
+```text
+��Ŀ: �ڸ�����������nums��,�ҳ��˻���������������(�������������ٰ���һ������),�����ظ�����������Ӧ�ĳ˻�;
+    ����: [2,3,-2,4]
+    ���: 6
+    ����: ������ [2,3] �����˻� 6
+    ����: [-2,0,-1]
+    ���: 0
+    ����: �������Ϊ 2, ��Ϊ [-2,-1] ����������
+1.��̬�滮:
+    [1]˼·:
+        (1)��������ʱ���㵱ǰ���ֵ�����ϸ���
+        (2)��imaxΪ��ǰ���ֵ,��ǰ���ֵΪ imax = max(imax * nums[i], nums[i])
+        (3)���ڴ��ڸ���,��ô�ᵼ�����ı���С��,��С�ı�����;
+            ��˻���Ҫά����ǰ��Сֵimin,imin=min(imin * nums[i], nums[i])
+        (4)����������ʱ��imax��imin���н����ٽ�����һ������;
+    [2]ʵ��:
+        class Solution {
+            public int maxProduct(int[] nums) {
+                // ������������: ���ֵ,ǰi��˻������ֵ,ǰi��˻�����Сֵ
+                int max = Integer.MIN_VALUE,imax =1,imin = 1;
+                // ��������
+                for (int num : nums) {
+                    // �����ǰ����ֵΪ����,��ǰi��˻������ֵ�����Сֵ,ǰi��˻�����Сֵ������ֵ
+                    // ������ǰi������ֵ��ǰi�����Сֵ
+                    if(num < 0){
+                        int temp = imax;
+                        imax = imin;
+                        imin = temp;
+                    }
+                    // ǰi��˻������ֵ
+                    imax = Math.max(imax*num,num);
+                    // ǰi��˻�����Сֵ
+                    imin = Math.min(imin*num,num);
+                    // ǰi���г˻��������������ֵ
+                    max = Math.max(max,imax);
+                }
+                return max;
+            }
+        }
+    [3]���Ӷȷ���:
+        (1)ʱ�临�Ӷ�: O(n)
+        (2)�ռ临�Ӷ�: O(1)
+```

-Original file line number
+Diff line change
@@ @@ -0,0 +1,43 @@ @@
 +```text
 +题目: 在给定整数数组nums中,找出乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积;
 +    输入: [2,3,-2,4]
 +    输出: 6
 +    解释: 子数组 [2,3] 有最大乘积 6
 +    输入: [-2,0,-1]
 +    输出: 0
 +    解释: 结果不能为 2, 因为 [-2,-1] 不是子数组
 +1.动态规划:
 +    [1]思路:
 +        (1)遍历数组时计算当前最大值，不断更新
 +        (2)令imax为当前最大值,则当前最大值为 imax = max(imax * nums[i], nums[i])
 +        (3)由于存在负数,那么会导致最大的变最小的,最小的变最大的;
 +            因此还需要维护当前最小值imin,imin=min(imin * nums[i], nums[i])
 +        (4)当负数出现时则imax与imin进行交换再进行下一步计算;
 +    [2]实现:
 +        class Solution {
 +            public int maxProduct(int[] nums) {
 +                // 定义三个变量: 最大值,前i项乘积的最大值,前i项乘积的最小值
 +                int max = Integer.MIN_VALUE,imax =1,imin = 1;
 +                // 遍历数组
 +                for (int num : nums) {
 +                    // 如果当前遍历值为负数,则前i项乘积的最大值变成最小值,前i项乘积的最小值变成最大值
 +                    // 即交换前i项的最大值和前i项的最小值
 +                    if(num < 0){
 +                        int temp = imax;
 +                        imax = imin;
 +                        imin = temp;
 +                    }
 +                    // 前i项乘积的最大值
 +                    imax = Math.max(imax*num,num);
 +                    // 前i项乘积的最小值
 +                    imin = Math.min(imin*num,num);
 +                    // 前i项中乘积最大的子数组最大值
 +                    max = Math.max(max,imax);
 +                }
 +                return max;
 +            }
 +        }
 +    [3]复杂度分析:
 +        (1)时间复杂度: O(n)
 +        (2)空间复杂度: O(1)
 +```