算法练习6

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

解题思路

题目大意：寻找最大连续子数组和

最近在练dp，这道题可以用dp来解，首先定义状态，dp[i]是以元素i结尾的和最大的子数组。接下来定义状态转移方程：dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i -1] : 0);

代码

public class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = max > dp[i] ? max : dp[i];
        }
        return max;
    }
}

---

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

解题思路

题目大意：爬n步楼梯，一次可以爬一步或者两步，求有几种方法爬到n层

设dp[i]为爬i层的方法数，那么可以得到状态转移方程：dp[i] = dp[i - 1] + dp [i - 2]; (i>2)特殊的：dp[1]=1、dp[2]=2 。

代码

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3;i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

---

Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

解题思路

题目大意：给定股票每日的售价，求 一次买进和一次卖出最多可以获取多大利润。

每次更新最大差价和最小价格。

代码

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int ans = 0;
        int money = prices[0];
        for (int i = 1; i < prices.length; i++) {
            ans = Math.max(ans, prices[i] - money);
            money = Math.min(prices[i], money);
        }
        return ans;
    }
}

---

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

解题思路

题目大意：一排房子，不能在一晚同时抢劫相邻的房子，求一晚最大收益。

思路：对于每个房子，都有两个状态，抢或者不抢。如果抢当前房子，那么收益为不抢上一个房子的收益加当前房子的收益；如果不抢，那么当前收益为上一个房子抢的收益和不抢的收益中大的那个。

代码

public class Solution {
    public int rob(int[] nums) {
        int rob = 0; 
        int notrob = 0; 
        for(int i=0; i<num.length; i++) {
            int currob = notrob + num[i]; 
            notrob = Math.max(notrob, rob); 
            rob = currob;
        }
        return Math.max(rob, notrob);
    }
}

---

Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

解题思路

题目大意：给定一个数组，求sum(i,j)。

由于对象实例化之后数组是不会变的，所以定义sum[i]是前i个元素的和，sum[i] = sum[i - 1] + nums[i];

代码

public class NumArray {

    private int[] sum;
    
    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}