1. LEETCODE 338
   Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
   Example:For num = 5
   you should return [0,1,1,2,1,2]

解法：

避免重复计算，当前结果依赖于历史结果。

public class Solution {
    public int[] countBits(int num) {
        int[] result = new int[num+1];
        result[0]=0;
        for(int i=0;i<=num;i++){
            result[i] = result[i/2]+i%2;
        }
        return result;
    }
}

---

2. LEETCODE 53
   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

解法：

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

3.LEETCODE 121
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.

解法

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

4.LEETCODE 198
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) {
        if(nums == null || nums.length == 0) {
            return 0;
        } else if(nums.length == 1){
            return nums[0];
        } else if(nums.length == 2){
            return Math.max(nums[0],nums[1]);
        }
        int result = 0;
        //动态规划
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = nums[2] + nums[0];
        for(int i = 3;i<nums.length;i++){
            dp[i] = nums[i] + Math.max(dp[i-2],dp[i-3]);
        }
        return Math.max(dp[nums.length - 1], dp[nums.length - 2]);
    }
}