feat: [贪心] 53

chen-shiwei · chen-shiwei · commit 8405b9a480e1 · 2021-06-04T23:35:06.000+08:00
diff --git a/leetcode/53.最大子序和/maxSubArray.go b/leetcode/53.最大子序和/maxSubArray.go
diff --git a/leetcode/53.最大子序和_贪心_dp/maxSubArray.go b/leetcode/53.最大子序和_贪心_dp/maxSubArray.go
@@ -0,0 +1,76 @@
+package _3_最大子序和_贪心_dp
+
+import "math"
+
+func maxSubArray(nums []int) int {
+	l := len(nums)
+	var maxN = nums[0]
+	for i := 1; i < l; i++ {
+		if nums[i]+nums[i-1] > nums[i] {
+			nums[i] += nums[i-1]
+		}
+		maxN = max(nums[i], maxN)
+	}
+	return maxN
+}
+
+func maxSubArrayWithDP(nums []int) int {
+	l := len(nums)
+
+	var dp = make([]int, l)
+	dp[0] = nums[0]
+	var ans int
+	for i := 1; i < l; i++ {
+		if nums[i]+nums[i-1] > nums[i] {
+			nums[i] = nums[i] + nums[i-1]
+		}
+		if nums[i] > ans {
+			ans = nums[i]
+		}
+	}
+
+	return ans
+}
+
+func maxSubArrayWithGreedy(nums []int) int {
+	l := len(nums)
+
+	var ans int
+	var result = math.MinInt32
+	for i := 0; i < l; i++ {
+		ans += nums[i]
+		if ans > result {
+			result = ans
+		}
+
+		if ans < 0 {
+			ans = 0
+		}
+	}
+
+	return result
+}
+
+func maxSubArrayWithFor(nums []int) int {
+	l := len(nums)
+	var ans = math.MinInt32
+	for i := 0; i < l; i++ {
+		var tmp int
+		for j := i; j < l; j++ {
+			tmp += nums[j]
+			if tmp > ans {
+				ans = tmp
+			}
+		}
+	}
+
+	return ans
+}
+
+func max(a, b int) int {
+	if a >= b {
+		return a
+	}
+
+	return b
+}
diff --git a/leetcode/53.最大子序和_贪心_dp/maxSubArray_test.go b/leetcode/53.最大子序和_贪心_dp/maxSubArray_test.go
@@ -1,4 +1,4 @@
-package _3_最大子序和
+package _3_最大子序和_贪心_dp
 
 import "testing"
 
@@ -17,7 +17,7 @@ func Test_maxSubArray(t *testing.T) {
 	}
 	for _, tt := range tests {
 		t.Run(tt.name, func(t *testing.T) {
-			if got := maxSubArray(tt.args.nums); got != tt.want {
+			if got := maxSubArrayWithGreedy(tt.args.nums); got != tt.want {
 				t.Errorf("maxSubArray() = %v, want %v", got, tt.want)
 			}
 		})

Original file line number	Diff line number	Diff line change
`@@ -1,4 +1,4 @@`
`1`		`-package _3_最大子序和`
	`1`	`+package _3_最大子序和_贪心_dp`
`2`	`2`
`3`	`3`	`import "testing"`
`4`	`4`
`@@ -17,7 +17,7 @@ func Test_maxSubArray(t *testing.T) {`
`17`	`17`	`}`
`18`	`18`	`for _, tt := range tests {`
`19`	`19`	`t.Run(tt.name, func(t *testing.T) {`
`20`		`- if got := maxSubArray(tt.args.nums); got != tt.want {`
	`20`	`+ if got := maxSubArrayWithGreedy(tt.args.nums); got != tt.want {`
`21`	`21`	`t.Errorf("maxSubArray() = %v, want %v", got, tt.want)`
`22`	`22`	`}`
`23`	`23`	`})`