Algorithms: Greedy

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

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int reach = 0;
        for (auto i = 0; i != nums.size() && i <= reach; ++i) {
            reach = max(reach, nums[i] + i);
        }

        return reach >= nums.size() - 1;
    }
};

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:
You can assume that you can always reach the last index.

class Solution {
public:
    int jump(vector<int>& nums) {
        int reach = 0, count = 0, next = 0;
        for (auto i = 0; i < nums.size() - 1; ++i) {
            reach = max(reach, i + nums[i]);
            if (i == next) {
                count++;
                next = reach;
            }
        }
        return count;
    }
};

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int n = gas.size();
    int total = 0, subsum = INT_MAX, start = 0;
    for (int i = 0; i < n; ++i) {
        total += (gas[i] - cost[i]);
        if (total < subsum) {
            subsum = total;
            start = i + 1;
        }
    }

    return (total >= 0) ? start%n : -1;
}

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

int candy(vector<int>& ratings) {
    if (ratings.size() <= 1) return ratings.size();

    int res = 0;
    vector<int> counts(ratings.size(), 1);
    for (auto i = 0; i < ratings.size() - 1; ++i) {
        if (ratings[i + 1] > ratings[i])
            counts[i + 1] = counts[i] + 1;
    }

    for (auto i = ratings.size() - 1; i > 0; --i) {
        if (ratings[i - 1] > ratings[i])
            counts[i - 1] = max(counts[i - 1], counts[i] + 1);
    }

    for (auto n:counts)
        res += n;
    return res;
}