Dynamic Programming（动态规划）
53. Maximum Subarray
最大和子数组（元素连续）
例如题目中给出的例子：
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
代码：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int currentSum = 0, maxvalue = INT_MIN;
for(int i = 0; i < nums.size(); ++i )
{
currentSum = max(currentSum + nums[i], nums[i]);
maxvalue = max(maxvalue,currentSum);
}
return maxvalue;
}
};
思路：
currentSum 是加到第i个元素为止的最大和，maxvalue 是以0,1,2,3……i个元素结尾的currentSum中最大的currentSum
53.png
动态规划一般解题思路是
（1）将原问题分解为子问题
（2）确定状态和初始条件
（3）构造状态转移方程
一开始接触动态规划，建议小伙伴们将注意力集中在怎么样将原问题规模缩小为子问题，多接触一些不同类型动归题目，多动手画图表或示意图，培养分解问题的直觉。
Greedy（贪婪算法）
55. Jump Game
给定一个非负整数的数组，每个数字表示在当前位置的基础上最多可以走的步数，求判断能不能到达最后一个位置。
Input: [2,3,1,1,4]
在第一个元素2处，可以走到第二个元素3，也可以走到第三个元素1
class Solution {
public:
bool canJump(vector<int>& nums) {
//reach为以当前元素为起点所能达到的最远元素位置
int n = nums.size(), reach = 0;
for (int i = 0; i < n; ++i) {
//如果不能到达第i个元素或者reach已经达到最后一个元素，则退出
if (i > reach || reach >= n - 1) break;
//计算当前元素所能到达的最远元素位置
reach = max(reach, i + nums[i]);
cout<<i<<endl;
}
cout<<reach<<endl;
return reach >= n - 1;
}
};
贪婪算法，顾名思义，就是考虑当前每个元素所能达到的最远距离，满足条件就可以返回，下面是例子[2,3,1,1,4]的示意图
55 (1).png
遍历数组中的每个元素，查看每个元素所能到达的最远距离，满足条件就返回，继续看例子[3,2,1,0,4]的示意图：
55-1.png
怎样应对IT面试与笔试-（一）
怎样应对IT面试与笔试-（二）
怎样应对IT面试与笔试-（三）
怎样应对IT面试与笔试-（四）
怎样应对IT面试与笔试-（五）
怎样应对IT面试与笔试-（五-1）
怎样应对IT面试与笔试-（六）
怎样应对IT面试与笔试-（七）
怎样应对IT面试与笔试-（八）
怎样应对IT面试与笔试-（九）
怎样应对IT面试与笔试-（十）
怎样应对IT面试与笔试-（十一）
怎样应对IT面试与笔试-（十二）
怎样应对IT面试与笔试-（十三）
怎样应对IT面试与笔试-（十四）
怎样应对IT面试与笔试-（十五）
怎样应对IT面试与笔试-（十六）
