贪心

1.基础知识

贪心算法是针对要解决的问题，先做出选择，再解决剩下的子问题。将子问题的最优解和我们所作的贪心选择联合起来，就可以得出原问题的最优解，即全局最优解可以通过局部最优（贪心）选择来达到。

贪心与动规的区别： 在动态规划中，每一步做出的选择都依赖于子问题的解，因此解动态规划一般是自底向上的。 而贪心算法中，我们所做的当前选择可能依赖于已经做出的所有选择，但不依赖于子问题的解，因此通常是自顶向下的。

2.应用连续子数组的最大和

题目:输入一个整型数组, 数组里有正数也有负数. 数组中一个或连续的多个整数组成一个子数组. 求所有子数组的和的最大值. 要求时间复杂度为 O(n)

贪心法：

依次遍历数组，若当前和为正数，则加上后面数字可能会组成连续子数组的最大和；若当前和为负数，则将其置0.

#include<iostream> #include<vector> using namespace std; int getMaxSum(const vector<int> &v); int main() { vector<int> v1={-2, 5, 3, -6, 4, -8, 6}; vector<int> v2={-2, -5, -3, -6, -4, -8, -6}; vector<int> v3={2, 5, 3, 6, 4, 8, 6}; vector<int> v4; cout << getMaxSum(v1) << endl; cout << getMaxSum(v2) << endl; cout << getMaxSum(v3) << endl; cout << getMaxSum(v4) << endl; return 0; } int getMaxSum(const vector<int> &v) { int len=v.size(); int tempSum=0; int maxSum=0; for(int i=0; i<len; i++) { tempSum += v.at(i); if(tempSum<0) tempSum=0; if(maxSum<tempSum) maxSum=tempSum; } return maxSum; }

动态规划法：

用函数 f(i) 表示以第i个数字结尾的子数组的最大和，那么我们可以求出 max(f(i)) 。我们可用如下递推公式求 f(i) :

f(i)={pData[i]i=0或f(i−1)⩽0f(i−1)+pData[i]i≠0或f(i−1)>0 这个公式的意义：当以第i-1个数字结尾的子数组中所有数字的和小于0时，如果把这个负数与第i个数累加，得到的结果比第i个数字本身还要小，所以这种情况下以第i个数字结尾的子数组就是第i个数字本身。如果以第i-1个数字结尾的子数组中所有数字的和大于0，与第i个数字累加就得到以第i个数字结尾的子数组中所有数字的和。

#include<iostream> #include<vector> #include<algorithm> using namespace std; int getMaxSum(const vector<int> &v); int main() { vector<int> v1={-2, 5, 3, -6, 4, -8, 6}; vector<int> v2={-2, -5, -3, -6, -4, -8, -6}; vector<int> v3={2, 5, 3, 6, 4, 8, 6}; vector<int> v4; cout << getMaxSum(v1) << endl; cout << getMaxSum(v2) << endl; cout << getMaxSum(v3) << endl; cout << getMaxSum(v4) << endl; return 0; } int getMaxSum(const vector<int> &v) { int len=v.size(); if(len <= 0) return 0; vector<int> f(len); f.at(0)=v.at(0); for(int i=1; i<len; i++) { if(f.at(i-1)<=0) f.at(i)=v.at(i); else f.at(i)=f.at(i-1)+v.at(i); } return *max_element(f.begin(), f.end() ); }