怎样应对IT面试与笔试-（十）

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面试与笔试-（十六）