leetcode:53. Maximum Subarray
2018-08-20 本文已影响0人
唐僧取经
53. Maximum Subarray
Description
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Answer
package main
import "fmt"
func maxSubArray(nums1 []int) int {
var nums []int
nums = append(nums, nums1...)
if len(nums) == 1 {
return nums[0]
}
max := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i-1]+nums[i] > nums[i] {
nums[i] += nums[i-1]
}
}
for j := 0; j < len(nums); j++ {
if max < nums[j] {
max = nums[j]
}
}
return max
}
func main() {
arr := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
fmt.Println(maxSubArray(arr))
fmt.Println(arr)
}