前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode53-Maximum Subarray

LeetCode53-Maximum Subarray

作者头像
Dylan Liu
发布2019-07-01 12:00:34
5190
发布2019-07-01 12:00:34
举报
文章被收录于专栏:dylanliu

Description

tags : Divide And Conquer Dynamic Programming Array

Difficulties : easy

代码语言:javascript
复制
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.

Solution

穷举法

这道题标为简单的原因应该就是使用穷举法是可以Accepted的,我们将所有的连续子串穷举之后取最大值就可以了。需要两个for循环,时间复杂度O(n^2), 空间复杂度O(1)

DP + 贪婪

这个解法是由Jon Bentley (Sep. 1984 Vol. 27 No. 9 Communications of the ACM P885) 给出的,下面摘录一下算法解释:

代码语言:javascript
复制
algorithm that operates on arrays: it starts at the left end (element A[1]) and scans through to the right end (element A[n]), keeping track of the maximum sum subvector seen so far. The maximum is initially A[0]. Suppose we've solved the problem for A[1 .. i - 1]; how can we extend that to A[1 .. i]? The maximum
sum in the first I elements is either the maximum sum in the first i - 1 elements (which we'll call MaxSoFar), or it is that of a subvector that ends in position i (which we'll call MaxEndingHere).

MaxEndingHere is either A[i] plus the previous MaxEndingHere, or just A[i], whichever is larger.

也就是说这是一个动态规划 + 贪婪的算法,时间复杂度只需要 O(n),空间复杂度为 O(1),算得上是完美解法了

代码语言:javascript
复制
func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    maxSoFar := nums[0]
    maxEndHere := nums[0]
    
    for i:= 1; i< len(nums); i++ {
        maxEndHere = int( math.Max(float64(maxEndHere + nums[i]), float64(nums[i])))
        maxSoFar = int(math.Max(float64(maxSoFar), float64(maxEndHere)))
    }
    
    return maxSoFar
}
Divide And Conquer

题目给出了要求使用分治法,我们来分析一下如何使用分治法

对于整形数组 nums, 分成左右两部分 numsLeft numsRight, 然后分别进行最大子串和的计算,当只有一个元素时,我们就返回这个元素,关键问题来了,如何合并两部分来得到最终的结果呢?(divide and conquer 里最难就是conquer部分了)

这里我先去看了一下 divide and conquer 的 Wikipedia 字条,里面列出了很多使用分治法的经典算法案例,这个题目与 Closest Pair Of Points problem 是很相似的。

两个子串的 conquer 需要的条件有:

  • 左侧和右侧都需要有元素参数
  • 从两个子串的中心向左向右得出一个最大元素和m

左侧、右侧与m的最大值就是原数组的最大子串和。

代码语言:javascript
复制
func maxSubArray(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}

	return divideAndConquer(nums, 0, len(nums))
}

func divideAndConquer(nums []int, from, end int) int {
	if end-from == 1 {
		return nums[from]
	}
	middle := from + (end-from)/2

	maxLeft := divideAndConquer(nums, from, middle)
	maxRight := divideAndConquer(nums, middle, end)

	continuousMax := continuousMaxLeft(nums, from, middle) + continuousMaxRight(nums, middle, end)

	return max(max(maxLeft, maxRight), continuousMax)
}

func continuousMaxLeft(nums []int, from, end int) int {
	m := nums[end-1]
	cm := m
	for i := end - 2; i >= from; i-- {
		cm = cm+nums[i]
		m = max(m, cm)
	}
	return m;
}

func continuousMaxRight(nums []int, from, end int) int {
	m := nums[from]
	cm := m
	for i := from + 1; i < end; i++ {
		cm = cm+nums[i]
		m = max(m, cm)
	}
	return m
}
func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Description
  • Solution
    • 穷举法
      • DP + 贪婪
        • Divide And Conquer
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档