贪心算法

• 贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

• 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

• 在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

• 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

• 贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

• 贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。 所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

贪心算法的基本思路

1. 建立数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每一子问题求解，得到子问题的局部最优解。
4. 把子问题的解局部最优解合成原来解问题的一个解

应用场景

贪心策略适用的前提是：局部最优策略能导致产生全局最优解

go 实现贪心算法

• 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

  • 示例: 输入: [-2,1,-3,4,-5,2,1,-1,4], 输出: 6

  • 解释: 连续子数组 [2,1,-1,4] 的和最大，为 6

  • 解题思路：遍历数组，判断相邻的值之和是否大于0，若大于0则继续遍历，反之则重新开始遍历

  package main
  
  import (
  	"fmt"
  )
  
  func main() {
  	var numArr = []int{-2, 1, -3, 4, -5, 2, 1, -1, 4}
  	//numArr = []int{-2, 1, -3, 4, -3, 4, 2, -5, 4}
  	totalNum := maxAddArray(numArr)
  	fmt.Println("最大连续之和为:", totalNum)
  }
  
  func maxAddArray(numArr []int) int {
  	if len(numArr) == 1 {
  		return numArr[0]
  	}
  
  	var currentSum, maxSum = 0, numArr[0]
  	for _, item := range numArr {
  		if currentSum > 0 {
  			currentSum += item
  		} else {
  			currentSum = item
  		}
  		if currentSum > maxSum {
  			maxSum = currentSum
  		}
  	}
  
  	return maxSum
  }