{"id":330,"date":"2012-05-17T14:30:28","date_gmt":"2012-05-17T06:30:28","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=330"},"modified":"2020-06-06T14:31:22","modified_gmt":"2020-06-06T06:31:22","slug":"%e6%9c%80%e5%a4%a7%e5%ad%90%e6%ae%b5%e5%92%8c%e7%9a%84%e7%ae%80%e5%8d%95%e3%80%81%e5%88%86%e6%b2%bb%e4%b8%8e%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%e8%a7%a3%e6%b3%95","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=330","title":{"rendered":"\u6700\u5927\u5b50\u6bb5\u548c\u7684\u7b80\u5355\u3001\u5206\u6cbb\u4e0e\u52a8\u6001\u89c4\u5212\u89e3\u6cd5"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>\/\/\u6700\u5927\u5b50\u6bb5\u548c_\u7b80\u5355\u89e3\u6cd5\npackage wkx;\n \nimport java.io.IOException;\n \npublic class Test { \n\t\n\tprivate static int MaxSum(int&#91;] a,Point p) {\n\t\tint len =a.length;\n\t\tint sum=0;\n\t\tint max=Integer.MIN_VALUE;\n\t\tfor(int i=0;i&lt;len;i++){\n\t\t\tfor(int j=i;j&lt;len;j++){\n\t\t\t\tsum=0;\n\t\t\t\tfor(int k=i;k&lt;=j;k++){\n\t\t\t\t\tsum+=a&#91;k];\n\t\t\t\t}\n\t\t\t\tif(sum>max){\n\t\t\t\t\tmax=sum;\n\t\t\t\t\tp.x=i;\n\t\t\t\t\tp.y=j;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\treturn max;\n\t}\n\t\n\tprivate static class Point{\n\t\tprivate int x;\n\t\tprivate int y;\n\t}\n\t\n\tpublic static void main(String&#91;] args) throws IOException {\n\t\tint&#91;] a=new int&#91;]{-2,11,-4,13,-5,-2};\n\t\tPoint p=new Point();\n\t\tSystem.out.println(MaxSum(a,p));\n\t\tSystem.out.println(p.x+\" \"+p.y);\n\t}\n}\n \n \n\/\/\u6700\u5927\u5b50\u6bb5\u548c_\u7b80\u5355\u89e3\u6cd5\u6539\u8fdb\npackage wkx;\n \nimport java.io.IOException;\n \npublic class Test {\n \n\tprivate static int MaxSum(int&#91;] a, Point p) {\n\t\tint len = a.length;\n\t\tint max = Integer.MIN_VALUE;\n\t\tfor (int i = 0; i &lt; len; i++) {\n\t\t\tint sum = 0;\n\t\t\tfor (int j = i; j &lt; len; j++) {\n\t\t\t\tsum += a&#91;j];\n\t\t\t\tif (sum > max) {\n\t\t\t\t\tmax = sum;\n\t\t\t\t\tp.x = i;\n\t\t\t\t\tp.y = j;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\treturn max;\n\t}\n \n\tprivate static class Point {\n\t\tprivate int x;\n\t\tprivate int y;\n\t}\n \n\tpublic static void main(String&#91;] args) throws IOException {\n\t\tint&#91;] a = new int&#91;] { -2, 11, -4, 13, -5, -2 };\n\t\tPoint p = new Point();\n\t\tSystem.out.println(MaxSum(a, p));\n\t\tSystem.out.println(p.x + \" \" + p.y);\n\t}\n}\n \n \n\/\/\u6700\u5927\u5b50\u6bb5\u548c_\u5206\u6cbb\u89e3\u6cd5\npackage wkx;\n \nimport java.io.IOException;\n \npublic class Test {\n \n\tprivate static int MaxSum(int&#91;] a, int beg, int end) {\n\t\tif (beg == end) {\n\t\t\treturn a&#91;beg];\n\t\t}\n\t\tint mid = (beg + end) \/ 2;\n\t\tint leftSum = MaxSum(a, beg, mid);\n\t\tint rightSum = MaxSum(a, mid + 1, end);\n\t\tint sumLeft=0;\n\t\tint left=0;\n\t\tfor(int i=mid;i>=0;i--){\n\t\t\tleft+=a&#91;i];\n\t\t\tif(left>sumLeft){\n\t\t\t\tsumLeft=left;\n\t\t\t}\n\t\t}\n\t\tint sumRight=0;\n\t\tint right=0;\n\t\tfor(int i=mid+1;i&lt;=end;i++){\n\t\t\tright+=a&#91;i];\n\t\t\tif(right>sumRight){\n\t\t\t\tsumRight=right;\n\t\t\t}\n\t\t}\n\t\tint sum=sumLeft+sumRight;\n\t\tif(sum&lt;leftSum)\n\t\t\tsum=leftSum;\n\t\tif(sum&lt;rightSum)\n\t\t\tsum=rightSum;\n\t\treturn sum;\n\t}\n \n\tpublic static void main(String&#91;] args) throws IOException {\n\t\tint&#91;] a = new int&#91;] { -2, 11, -4, 13, -5, -2 };\n\t\tSystem.out.println(MaxSum(a, 0, a.length - 1));\n\t}\n}\n \n\/\/\u6700\u5927\u5b50\u6bb5\u548c_\u52a8\u6001\u89c4\u5212\u89e3\u6cd5\npackage wkx;\n \nimport java.io.IOException;\n \npublic class Test {\n \n\tprivate static int MaxSum(int&#91;] a,Point p) {\n\t\tint sum = 0, b = 0;\n\t\tfor (int i = 0; i &lt; a.length; i++) {\n\t\t\tif (b > 0) {\n\t\t\t\tb += a&#91;i];\n\t\t\t} else {\n\t\t\t\tp.x=i;\n\t\t\t\tb = a&#91;i];\n\t\t\t}\n\t\t\tif (b > sum) {\n\t\t\t\tp.y=i;\n\t\t\t\tsum = b;\n\t\t\t}\n\t\t}\n\t\treturn sum;\n\t}\n\t\n\tprivate static class Point{\n\t\tprivate int x;\n\t\tprivate int y;\n\t}\n\t\n\tpublic static void main(String&#91;] args) throws IOException {\n\t\tint&#91;] a = new int&#91;] { -2, 11, -4, 13, -5, -2 };\n\t\tPoint p=new Point();\n\t\tSystem.out.println(MaxSum(a,p));\n\t\tSystem.out.println(p.x+\" \"+p.y);\n\t}\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-330","post","type-post","status-publish","format-standard","hentry","category-06-03-play-ground"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/330","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=330"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/330\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=330"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=330"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=330"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}