{"id":2554,"date":"2022-03-30T22:26:43","date_gmt":"2022-03-30T14:26:43","guid":{"rendered":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2554"},"modified":"2022-03-30T23:20:03","modified_gmt":"2022-03-30T15:20:03","slug":"dp%e7%ac%ac%e5%85%ad%e5%a4%a9","status":"publish","type":"post","link":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2554","title":{"rendered":"dp\u7b2c\u516d\u5929"},"content":{"rendered":"\n

\u300c\u52a8\u6001\u89c4\u5212\u300d – \u5b66\u4e60\u8ba1\u5212 – \u529b\u6263\uff08LeetCode\uff09\u5168\u7403\u6781\u5ba2\u631a\u7231\u7684\u6280\u672f\u6210\u957f\u5e73\u53f0 (leetcode-cn.com)<\/a><\/p>\n\n\n\n

152. \u4e58\u79ef\u6700\u5927\u5b50\u6570\u7ec4<\/a><\/p>\n\n\n\n

\u8fd9\u9898\u548c\u6700\u5927\u5b50\u6570\u7ec4\u548c\u7684\u533a\u522b\u5728\u4e8e\uff0c\u4e58\u6cd5\uff0c\u8d1f\u6570\u6709\u673a\u4f1a\u53d8\u6210\u6700\u5927\u3002\u6240\u4ee5\u4e24\u4e2a\u53d8\u91cf\uff0c\u6700\u5927\u548c\u6700\u5c0f\u90fd\u8981\u4fdd\u7559\u3002\u53e6\u5916for\u5faa\u73af\u91cc\u9762\u6ce8\u610f\u5c0f\u7ec6\u8282\uff1a\/\/ \u9632\u6b62\u8ba1\u7b97\u7ed3\u679c\u53c2\u4e0e\u540e\u7eed\u8ba1\u7b97 int premax = max; int premin = min; <\/mark><\/p>\n\n\n\n

\/**\n 152. \u4e58\u79ef\u6700\u5927\u5b50\u6570\u7ec4\n \u7ed9\u4f60\u4e00\u4e2a\u6574\u6570\u6570\u7ec4 nums \uff0c\u8bf7\u4f60\u627e\u51fa\u6570\u7ec4\u4e2d\u4e58\u79ef\u6700\u5927\u7684\u975e\u7a7a\u8fde\u7eed\u5b50\u6570\u7ec4\uff08\u8be5\u5b50\u6570\u7ec4\u4e2d\u81f3\u5c11\u5305\u542b\u4e00\u4e2a\u6570\u5b57\uff09\uff0c\u5e76\u8fd4\u56de\u8be5\u5b50\u6570\u7ec4\u6240\u5bf9\u5e94\u7684\u4e58\u79ef\u3002\n\n \u6d4b\u8bd5\u7528\u4f8b\u7684\u7b54\u6848\u662f\u4e00\u4e2a 32-\u4f4d \u6574\u6570\u3002\n\n \u5b50\u6570\u7ec4 \u662f\u6570\u7ec4\u7684\u8fde\u7eed\u5b50\u5e8f\u5217\u3002\n\n\n\n \u793a\u4f8b 1:\n\n \u8f93\u5165: nums = [2,3,-2,4]\n \u8f93\u51fa: 6\n \u89e3\u91ca: \u5b50\u6570\u7ec4 [2,3] \u6709\u6700\u5927\u4e58\u79ef 6\u3002\n \u793a\u4f8b 2:\n\n \u8f93\u5165: nums = [-2,0,-1]\n \u8f93\u51fa: 0\n \u89e3\u91ca: \u7ed3\u679c\u4e0d\u80fd\u4e3a 2, \u56e0\u4e3a [-2,-1] \u4e0d\u662f\u5b50\u6570\u7ec4\u3002\n\n\n \u63d0\u793a:\n\n 1 <= nums.length <= 2 * 10^4\n -10 <= nums[i] <= 10\n nums \u7684\u4efb\u4f55\u524d\u7f00\u6216\u540e\u7f00\u7684\u4e58\u79ef\u90fd \u4fdd\u8bc1 \u662f\u4e00\u4e2a 32-\u4f4d \u6574\u6570\n\n * <\/em>@author <\/em><\/strong>zeroheart\n *\n *\/\n<\/em>public class Question152 {\n    public int maxProduct(int[] nums) {\n        int max = nums[0];\n        \/\/ \u4e58\u6cd5\uff0c\u6700\u5c0f\u7684\u4e58\u4ee5nums[i]\uff0c\u53ef\u80fd\u53d8\u6210\u6700\u5927\u7684\n        int min = nums[0];\n        int result = nums[0];\n        int len = nums.length;\n\n        if(len==1)return result;\n\n        for(int i=1; i<len; i++){\n\/\/ \u9632\u6b62\u8ba1\u7b97\u7ed3\u679c\u53c2\u4e0e\u540e\u7eed\u8ba1\u7b97\n            int premax = max; int premin = min; \n            max = Math.max<\/em>(nums[i] * premax, Math.max<\/em>(nums[i] * premin, nums[i]));\n            min = Math.min<\/em>(nums[i] * premin, Math.min<\/em>(nums[i] * premax, nums[i]));\n\n            result = Math.max<\/em>(result, max);\n        }\n\n        return result;\n    }\n\n    public static void main(String[] args) {\n\n    }\n}<\/pre>\n\n\n\n
1567. \u4e58\u79ef\u4e3a\u6b63\u6570\u7684\u6700\u957f\u5b50\u6570\u7ec4\u957f\u5ea6<\/a><\/p>\n\n\n\n
\u8fd9\u9898\u4e5f\u662f\u6d89\u53ca\u4e00\u4e2a\u4e58\u6cd5\u53d8\u53f7\u7684\u95ee\u9898\u3002<\/p>\n\n\n\n
1567. \u4e58\u79ef\u4e3a\u6b63\u6570\u7684\u6700\u957f\u5b50\u6570\u7ec4\u957f\u5ea6
<\/em> \u7ed9\u4f60\u4e00\u4e2a\u6574\u6570\u6570\u7ec4 nums \uff0c\u8bf7\u4f60\u6c42\u51fa\u4e58\u79ef\u4e3a\u6b63\u6570\u7684\u6700\u957f\u5b50\u6570\u7ec4\u7684\u957f\u5ea6\u3002
<\/em>
<\/em> \u4e00\u4e2a\u6570\u7ec4\u7684\u5b50\u6570\u7ec4\u662f\u7531\u539f\u6570\u7ec4\u4e2d\u96f6\u4e2a\u6216\u8005\u66f4\u591a\u4e2a\u8fde\u7eed\u6570\u5b57\u7ec4\u6210\u7684\u6570\u7ec4\u3002
<\/em>
<\/em> \u8bf7\u4f60\u8fd4\u56de\u4e58\u79ef\u4e3a\u6b63\u6570\u7684\u6700\u957f\u5b50\u6570\u7ec4\u957f\u5ea6\u3002
<\/em>
<\/em>
<\/em>
<\/em> \u793a\u4f8b  1\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1anums = [1,-2,-3,4]
<\/em> \u8f93\u51fa\uff1a4
<\/em> \u89e3\u91ca\uff1a\u6570\u7ec4\u672c\u8eab\u4e58\u79ef\u5c31\u662f\u6b63\u6570\uff0c\u503c\u4e3a 24 \u3002
<\/em> \u793a\u4f8b 2\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1anums = [0,1,-2,-3,-4]
<\/em> \u8f93\u51fa\uff1a3
<\/em> \u89e3\u91ca\uff1a\u6700\u957f\u4e58\u79ef\u4e3a\u6b63\u6570\u7684\u5b50\u6570\u7ec4\u4e3a [1,-2,-3] \uff0c\u4e58\u79ef\u4e3a 6 \u3002
<\/em> \u6ce8\u610f\uff0c\u6211\u4eec\u4e0d\u80fd\u628a 0 \u4e5f\u5305\u62ec\u5230\u5b50\u6570\u7ec4\u4e2d\uff0c\u56e0\u4e3a\u8fd9\u6837\u4e58\u79ef\u4e3a 0 \uff0c\u4e0d\u662f\u6b63\u6570\u3002
<\/em> \u793a\u4f8b 3\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1anums = [-1,-2,-3,0,1]
<\/em> \u8f93\u51fa\uff1a2
<\/em> \u89e3\u91ca\uff1a\u4e58\u79ef\u4e3a\u6b63\u6570\u7684\u6700\u957f\u5b50\u6570\u7ec4\u662f [-1,-2] \u6216\u8005 [-2,-3] \u3002
<\/em>
<\/em>
<\/em> \u63d0\u793a\uff1a
<\/em>
<\/em> 1 <= nums.length <= 10^5
<\/em> -10^9 <= nums[i] <= 10^9
<\/em>
<\/em>
<\/em> * <\/em>@author <\/em><\/strong>zeroheart
<\/em> *
<\/em> *\/
<\/em>public class Question1567 {
    public int getMaxLen(int[] nums) {
        \/\/ \u8fd9\u4e2a\u867d\u7136\u662fdp\uff0c\u4f46\u5b9e\u9645\u4e0a\u7ed9\u4eba\u4e0d\u662fdp\u7684\u611f\u89c9
        int len = nums.length;
        \/\/ \u6b63\u6570\u957f\u5ea6
        int z = nums[0] > 0 ? 1 : 0;
        \/\/ \u8d1f\u6570\u957f\u5ea6
        int f = nums[0] < 0 ? 1 : 0;

        int max = z;


        for(int i = 1; i<len; i++){
            if(nums[i] > 0) {
                z = z + 1;
                f = f > 0 ? f + 1 : 0;
            }else if(nums[i] < 0) {
                \/\/ int newz = f > 0 ? f + 1 : 0;
                \/\/ int newf = z + 1;
                \/\/ z = newz;
                \/\/ f = newf;

                int temp = z;
                z = f;
                f = temp;

                z = z > 0 ? z + 1 : 0;
                f = f + 1;
            }else{
                z = 0;
                f = 0;
            }

            max = Math.max<\/em>(max, z);
        }

        return max;
    }

    public static void main(String[] args) {

    }
}<\/pre>\n","protected":false},"excerpt":{"rendered":"
\u300c\u52a8\u6001\u89c4\u5212\u300d – \u5b66\u4e60\u8ba1\u5212 – \u529b\u6263\uff08LeetCode\uff09\u5168\u7403\u6781\u5ba2\u631a\u7231\u7684\u6280\u672f\u6210\u957f\u5e73\u53f0 ( […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[155],"tags":[158],"_links":{"self":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2554"}],"collection":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2554"}],"version-history":[{"count":8,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2554\/revisions"}],"predecessor-version":[{"id":2562,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2554\/revisions\/2562"}],"wp:attachment":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2554"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2554"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2554"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}