Commitfbc8eb1

committed

53-maximum-subarray.md AddedSolution 1: Greedy Algorithm

1 parenta50eb27 commitfbc8eb1Copy full SHA for fbc8eb1

File tree

+35

-5

lines changed

+35

-5

lines changed

Lines changed: 18 additions & 3 deletions

Original file line number	Diff line number	Diff line change
`@@ -35,7 +35,7 @@ Constraints:`
`35`	`35`	```
`36`	`36`
`37`	`37`	`##Thoughts`
`38`		-* This problem can be solved by using`greedy algorithm`, but here we will use another way.
	`38`	+* This problem can be solved by using`greedy algorithm` (please see`solution 1` in Python), but here we will use another way.
`39`	`39`	* Imagine the size of nums is`i`, let us consider if the same question is applied to the`subarray` of`nums` from index`0` to`i - 1`.
`40`	`40`	* The answer is`yes`. Then let us think if the`i - 1`'s answer could impact the answer of`i`.
`41`	`41`	* The answer is still`yes`. What would be the impact?
`@@ -103,14 +103,29 @@ public class Solution`
`103`	`103`	```
`104`	`104`
`105`	`105`	`##Python`
	`106`	`+###Solution 1: Greedy Algorithm`
`106`	`107`	```python
`107`	`108`	`classSolution:`
`108`	`109`	`defmaxSubArray(self,nums: List[int]) ->int:`
`109`		`- dp= nums.copy()`
	`110`	`+ result=-float('inf')`
	`111`	`+ pre_sum=0`
	`112`	`+`
	`113`	`+for numin nums:`
	`114`	`+ pre_sum=max(pre_sum+ num, num)`
	`115`	`+ result=max(result, pre_sum)`
`110`	`116`
	`117`	`+return result`
	`118`	+```
	`119`	`+`
	`120`	`+###Solution 2: Dynamic Programming`
	`121`	+```python
	`122`	`+classSolution:`
	`123`	`+defmaxSubArray(self,nums: List[int]) ->int:`
	`124`	`+ dp= nums.copy()`
	`125`	`+`
`111`	`126`	`for iinrange(1,len(dp)):`
`112`	`127`	`dp[i]=max(nums[i], dp[i-1]+ nums[i])`
`113`		`-`
	`128`	`+`
`114`	`129`	`returnmax(dp)`
`115`	`130`	```
`116`	`131`

Lines changed: 17 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -103,14 +103,29 @@ public class Solution`
`103`	`103`	```
`104`	`104`
`105`	`105`	`##Python`
	`106`	`+###Solution 1: Greedy Algorithm`
`106`	`107`	```python
`107`	`108`	`classSolution:`
`108`	`109`	`defmaxSubArray(self,nums: List[int]) ->int:`
`109`		`- dp= nums.copy()`
	`110`	`+ result=-float('inf')`
	`111`	`+ pre_sum=0`
	`112`	`+`
	`113`	`+for numin nums:`
	`114`	`+ pre_sum=max(pre_sum+ num, num)`
	`115`	`+ result=max(result, pre_sum)`
`110`	`116`
	`117`	`+return result`
	`118`	+```
	`119`	`+`
	`120`	`+###Solution 2: Dynamic Programming`
	`121`	+```python
	`122`	`+classSolution:`
	`123`	`+defmaxSubArray(self,nums: List[int]) ->int:`
	`124`	`+ dp= nums.copy()`
	`125`	`+`
`111`	`126`	`for iinrange(1,len(dp)):`
`112`	`127`	`dp[i]=max(nums[i], dp[i-1]+ nums[i])`
`113`		`-`
	`128`	`+`
`114`	`129`	`returnmax(dp)`
`115`	`130`	```
`116`	`131`

Comments

(0)