Leetcode - Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

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.

This problem... suggest reciting the answer.

func maxSubArray(arr []int) int {
    maxEnding := arr[0]
    maxSofar := arr[0]
    
    for i := 1; i < len(arr); i++ {
        maxEnding = max(arr[i], arr[i]+maxEnding)
        maxSofar = max(maxSofar, maxEnding)
    }

	return maxSofar
}

func max(a, b int) int {
	if a < b {
		return b
	}

	return a
}

One comment in discussion:

• 相关文章
• 全局相关文章