基本题目

455. 分发饼干

贪心原则：将胃口大小从小到大排序，先给胃口最小的人尝试分配最小的饼干

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int i = 0, j = 0, r = 0;
        while (i < g.size() && j < s.size()) {
            if (g[i] <= s[j]) {
                i++;
                j++;
                r++;
            }
            else {
                j++;
            }
        }
        return r;
    }
};

376. 摆动序列

贪心原则：将数组分为若干段单调子序列，每次只取子序列的两端，也即判断有几个转折点

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) return 1;

        int up = 0;  // 0-equal, 1-up, -1-down
        int count = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) continue;
            if (!up || (nums[i] - nums[i - 1]) * up < 0) {
                count++;
                up = nums[i] - nums[i - 1];
            }
        }
        return count;
    }
};

也可以使用动态规划的思路求解，分别追踪最长的、末尾趋势为递增/递减的摆动序列

53. 最大子序和

经典解法：动态规划（以此为末尾元素的最大子序和）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int curr = 0, max = INT_MIN, n = nums.size();
        for (const int n : nums) {
            curr = curr > 0 ? curr + n : n;
            if (curr > max) max = curr;
        }
        return max;
    }
};

本题也可以使用贪心思想：什么时候舍弃负数？当且仅当它前面的正数不足以弥补该负数。因此可以从头开始累加，每次累加到负数，就将累加器清零，重新开始求和

此方法的证明过程见后文 [[#134. 加油站]]。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0, maxSum = INT_MIN;
        for (const int n : nums) {
            sum += n;
            if (sum > maxSum) maxSum = sum;
            if (sum < 0) sum = 0;
        }
        return maxSum;
    }
};

122. 买卖股票的最佳时机 II

将持有股票的时间段划分为长度为 1 的小区间，这样只需要找到那些递增的相邻价格即可。也可以这样考虑：每天都买入股票，可以选择当天卖出，也可以第二天卖出

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 1) return 0;
        int sum = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] > prices[i - 1])
                sum += (prices[i] - prices[i - 1]);
        }
        return sum;
    }
};

也可以使用动态规划解决，具体参考后续章节

55. 跳跃游戏

贪心：维护最远到达的位置

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size(), maxId = 0;
        for (int i = 0; i < n && i <= maxId; i++) {
            if (i + nums[i] > maxId) {
                maxId = i + nums[i];
            }
        }
        return maxId >= n - 1;
    }
};

45. 跳跃游戏 II

从前往后扩展：维护一个可以达到的范围，每次遍历其中的元素，将该范围向后延申，这样每次延伸部分所需要的跳跃次数就增加 1。直到达到最后一个元素为止

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), prev = 0, maxId = 0, maxStep = 1;
        if (n == 1) return 0;
        for (int i = 0; i < n && maxId < n - 1; i++) {
            if (i > prev) {
                // Reach another extension
                prev = maxId;
                maxStep++;
            }
            if (nums[i] + i > maxId) {
                // Extend
                maxId = nums[i] + i;
            }
        }
        return maxStep;
    }
};

1005. K 次取反后最大化的数组和

朴素贪心思想：每次取所有数中最小的，反转符号再放回数组中

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> q;
        for (const int n : nums) q.push(n);

        int v;
        for (int i = 0; i < k; i++) {
            v = -q.top();
            q.pop();
            q.push(v);
        }

        v = 0;
        while (!q.empty()) {
            v += q.top();
            q.pop();
        }

        return v;
    }
};

注意到，当 k 的值超过负数的数量时，在反转所有负数的符号之后，可以直接考虑剩余 k 的奇偶性，再操作最小的数即可

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());

        int sum = 0, n = nums.size();
        int minNum = INT_MAX;
        for (int num : nums) {
            if (k > 0 && num < 0) {
                num = -num;
                k--;
            }
            if (num < minNum) minNum = num;
            sum += num;
        }

        if (k % 2) sum -= 2 * minNum;
        return sum;
    }
};

134. 加油站

与最大子序和类似，本题要找一个起始点，从此开始的任意前缀和都非负。可以环形遍历数组，累加元素，遇到和为负则清零，直到区间首尾相接（满足题意）或区间起点超限。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        vector<int> nums(n);
        for (int i = 0; i < n; i++) nums[i] = gas[i] - cost[i];

        int i = -1, j = 0, sum = 0;
        while (i < n - 1) {
            // (i, j] sum >= 0
            sum += nums[j % n];
            if (sum < 0) {
                sum = 0;
                i = j;
            }
            if (j >= i + n) return i + 1;
            j++;
        }
        return -1;
    }
};

在官方题解中给出了具体证明，解释了为何遇到和为负时直接从下一个加油站开始检查：

假设有数组 $a[1..n]$，其中按照上述方法找到了一个局部最长的和非负子序列 $a[i..j]$，则 \(\sum\limits_{t=i}^{k}a_{t} \ge 0,\forall i \le k \le j\quad \sum\limits_{t=i}^{j+1}a_{t} <0\) 因此对于起始位置为 $k$ 的子序列，若 $i< k \le j$，则 \(\sum\limits_{t=k}^{j+1}a_{t}=\sum\limits_{t=i}^{j+1}a_{t} - \sum\limits_{t=i}^{k-1}a_{t} < 0\) 因此其满足条件的子序列一定更短，不再需要考虑。因此接下来考虑从 $j+1$ 开始的序列即可。