Commita05ec15

applewjg

committed

Maximum Subarray

Change-Id: I9b3057c4080dcaae52da93db46900274b3b0f0b0

1 parent4fe9f44 commita05ec15Copy full SHA for a05ec15

File tree

+33

-0

lines changed

+33

-0

lines changed

Lines changed: 33 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,33 @@`
	`1`	`+/*`
	`2`	`+ Author: King, wangjingui@outlook.com`
	`3`	`+ Date: Dec 25, 2014`
	`4`	`+ Problem: Maximum Subarray`
	`5`	`+ Difficulty: Medium`
	`6`	`+ Source: https://oj.leetcode.com/problems/maximum-subarray/`
	`7`	`+`
	`8`	`+ Find the contiguous subarray within an array (containing at least one number) which has the largest sum.`
	`9`	`+ For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.`
	`10`	`+`
	`11`	`+ Solution: dp.`
	`12`	`+ */`
	`13`	`+publicclassSolution {`
	`14`	`+publicintmaxSubArray_1(int[]A) {`
	`15`	`+if (A.length ==0)return0;`
	`16`	`+intminVal =Math.min(A[0],0),res =A[0],sum =A[0];`
	`17`	`+for (inti =1;i <A.length; ++i) {`
	`18`	`+sum +=A[i];`
	`19`	`+res =Math.max(res,sum -minVal);`
	`20`	`+minVal =Math.min(minVal,sum);`
	`21`	`+ }`
	`22`	`+returnres;`
	`23`	`+ }`
	`24`	`+publicintmaxSubArray_2(int[]A) {`
	`25`	`+if (A.length ==0)return0;`
	`26`	`+intdp =A[0],res =A[0];`
	`27`	`+for (inti =1;i <A.length; ++i) {`
	`28`	`+dp =Math.max(A[i],dp +A[i]);`
	`29`	`+res =Math.max(res,dp);`
	`30`	`+ }`
	`31`	`+returnres;`
	`32`	`+ }`
	`33`	`+}`

Comments

(0)