"122. The Best Time to Buy and Sell Stocks II"

You are given an integer array prices , where prices[i] represents the price of a certain stock on day i.

On each day, you can decide whether to buy and/or sell stocks. You can hold no more than one share of stock at any one time. You can also buy first and sell later on the same day.

Returns the maximum profit you can get.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
 Explanation: Buy on day 2 (stock price = 1) and sell on day 3 (stock price = 5), this trade can make profit = 5 - 1 = 4.
Then, buy on the 4th day (stock price = 3) and sell on the 5th day (stock price = 6), this transaction can make a profit = 6 - 3 = 3 .
     The total profit is 4 + 3 = 7 .

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the transaction can make profit = 5 - 1 = 4.
The total profit is 4 .

Example 3:

Input: prices = [7,6,4,3,1]
output: 0
 Explanation: In this case, the transaction cannot obtain a positive profit, so the maximum profit can be obtained by not participating in the transaction, and the maximum profit is 0.

//greedy:

// Greedy thinking
class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            result += Math.max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
}

//Dynamic programming:

class Solution { // dynamic programming
    public int maxProfit(int[] prices) {
        // [Number of days][Whether to hold stocks]
        int[][] dp = new int[prices.length][2];

        // base case
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            // dp formula
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }

        return dp[prices.length - 1][0];
    }
}

55. Jumping Game

Given an array nums of non-negative integers, you are initially at the first index of the array.

Each element in the array represents the maximum length you can jump at that position.

Determine whether you can reach the last subscript.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
 Explanation: You can jump 1 step first, from subscript 0 to subscript 1, and then jump 3 steps from subscript 1 to the last subscript.

Example 2:

Input: nums = [3,2,1,0,4]
output: false
 Explanation: No matter what, the position with subscript 3 will always be reached. But the maximum jump length for this subscript is 0 , so it is never possible to reach the last subscript.

class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        //Coverage, the initial coverage should be 0, because the following iterations start from subscript 0
        int coverRange = 0;
        //Update max coverage in coverage
        for (int i = 0; i <= coverRange; i++) {
            coverRange = Math.max(coverRange, i + nums[i]);
            if (coverRange >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

45. Jumping Game II

Given a zero-indexed integer array nums of length n. The initial position is nums[0].

Each element nums[i] represents the maximum length to jump forward from index i. In other words, if you are at nums[i], you can jump to any nums[i + j]:

• 0 <= j <= nums[i] 
• i + j < n

Returns the minimum number of hops to reach nums[n - 1]. Generated test cases can reach nums[n - 1].

Example 1:

enter: nums = [2,3,1,1,4]
output: 2
Explanation: The minimum number of hops to get to the last position is 2.
     Jump from index 0 to index 1, jump 1 step and jump 3 step to the last position of the array.

Example 2:

Input: nums = [2,3,0,1,4]
output: 2

// version one
class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }
        //Record the number of jumps
        int count=0;
        //Current maximum coverage area
        int curDistance = 0;
        //largest coverage area
        int maxDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            //Update the largest coverage area within the coverage area
            maxDistance = Math.max(maxDistance,i+nums[i]);
            //Indicates the current step, skip another step to reach the end
            if (maxDistance>=nums.length-1){
                count++;
                break;
            }
            //When reaching the maximum area currently covered, update the maximum area that can be reached in the next step
            if (i==curDistance){
                curDistance = maxDistance;
                count++;
            }
        }
        return count;
    }
}
// version two
class Solution {
    public int jump(int[] nums) {
        int result = 0;
        // The farthest distance subscript currently covered
        int end = 0;
        // Subscript of the furthest distance covered in the next step
        int temp = 0;
        for (int i = 0; i <= end && end < nums.length - 1; ++i) {
            temp = Math.max(temp, i + nums[i]);
            // The number of changes in the reachable position is the number of jumps
            if (i == end) {
                end = temp;
                result++;
            }
        }
        return result;
    }
}