152. Maximum Product Subarray.html

<html>
<head>
  <title>152. Maximum Product Subarray</title>
  <basefont face="Tahoma" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/304720 (en-US, DDL); Windows/10.0.14393 (Win64);"/>
  <style>
    body, td {
      font-family: Tahoma;
      font-size: 12pt;
    }
  </style>
</head>
<body>
<a name="8680"/>
<h1>152. Maximum Product Subarray</h1>
<div>
<table bgcolor="#D4DDE5" border="0">
<tr><td><b>Created:</b></td><td><i>3/14/2017 8:03 PM</i></td></tr>
<tr><td><b>Updated:</b></td><td><i>3/14/2017 10:07 PM</i></td></tr>
<tr><td><b>Tags:</b></td><td><i>leetcode tag</i></td></tr>
</table>
</div>
<br/>

<div>
<span><div><a href="https://leetcode.com/problems/maximum-product-subarray/#/description">https://leetcode.com/problems/maximum-product-subarray/#/description</a></div><div><br/></div><div>要求返回区间怎么办</div><div><br/></div><div>two state DP</div><div style="-en-codeblock: true; box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;"><div>public class Solution {</div><div>    public int maxProduct(int[] nums) {</div><div>        Integer posState = null;</div><div>        Integer negState = null;</div><div>        int max = 0;</div><div>        if (nums[0] &lt; 0) {</div><div>            negState = nums[0];</div><div>            max = negState;</div><div>        } else if (nums[0] &gt; 0) {</div><div>            posState = nums[0];</div><div>            max = posState;</div><div>        }</div><div><br/></div><div>        for (int i = 1; i &lt; nums.length; i++) {</div><div>            if (nums[i] &lt; 0) {</div><div>                Integer oldPosState = posState;</div><div>                if (negState == null) {</div><div>                    posState = null;</div><div>                } else {</div><div>                    posState = nums[i] * negState;</div><div>                    System.out.println(posState);</div><div>                    max = Math.max(posState, max);</div><div>                }</div><div>                if (oldPosState == null) {</div><div>                    negState = nums[i];</div><div>                    // max = Math.max(negState, max);</div><div>                } else {</div><div>                    negState = nums[i] * oldPosState;</div><div>                }</div><div>            } else if (nums[i] &gt; 0) {</div><div>                if (negState != null) {</div><div>                    negState = nums[i] * negState;</div><div>                }</div><div><br/></div><div>                if (posState == null) {</div><div>                    posState = nums[i];</div><div>                    max = Math.max(posState, max);</div><div>                } else {</div><div>                    posState = nums[i] * posState;</div><div>                    max = Math.max(posState, max);</div><div>                }</div><div>            } else {</div><div>                max = Math.max(0, max);</div><div>                posState = null;</div><div>                negState = null;</div><div>            }</div><div>        }</div><div>        return max;</div><div><br/></div><div>    }</div><div>}</div></div><div><br/></div><div>更好的方法</div><div style="-en-codeblock: true; box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;"><div>public class Solution {</div><div>public int maxProduct(int[] A) {</div><div>    if (A.length == 0) {</div><div>        return 0;</div><div>    }</div><div><br/></div><div>    int maxherepre = A[0];</div><div>    int minherepre = A[0];</div><div>    int maxsofar = A[0];</div><div>    int maxhere, minhere;</div><div><br/></div><div>    for (int i = 1; i &lt; A.length; i++) {</div><div>        maxhere = Math.max(Math.max(maxherepre * A[i], minherepre * A[i]), A[i]);</div><div>        minhere = Math.min(Math.min(maxherepre * A[i], minherepre * A[i]), A[i]);</div><div>        maxsofar = Math.max(maxhere, maxsofar);</div><div>        maxherepre = maxhere;</div><div>        minherepre = minhere;</div><div>    }</div><div>    return maxsofar;</div><div>}</div><div>}</div></div><div><br/></div></span>
</div></body></html>