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)
}