Leetcode - Dynamic Programming

53. Maximum Subarray

[-2,1,-3,4,-1,2,1,-5,4]
[-2,1,-2,4,3,5,6,1,5]
找从开头到每一个位置的最大值

//time: O(n)
class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        for(int i=1; i<nums.length; i++) {
            if(nums[i-1]>0) nums[i]+=nums[i-1];
            if(nums[i]>max) max=nums[i];
        }
        return max;
    }
}

121. Best Time to Buy and Sell Stock

思路：
[7,1,5,3,6,4] prices
[0,0,4,2,5,3] profit

//time: O(n)  space: O(n)
class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null || prices.length==0) return 0;
        int[] profit = new int[prices.length];
        profit[0]=0;
        int max = 0;
        for(int i=1; i<prices.length; i++) {
            if(prices[i]>prices[i-1] - profit[i-1]) {
                profit[i] = prices[i] - prices[i-1] + profit[i-1];   
            }else profit[i] = 0;
            max = Math.max(max, profit[i]);
        }
        return max;
    }
}

优化：

//time: O(n)  space: O(1)
class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null || prices.length==0) return 0;
        int max = 0;
        for(int i=1; i<prices.length; i++) {
            if(prices[i]>prices[i-1]) {
                max = Math.max(max, prices[i] - prices[i-1]);
                prices[i] = prices[i-1];   
            }
        }
        return max;
    }
}

5. Longest Palindromic Substring

遍历法：

class Solution {
    //time:O(n^2) space: O(n^2)
    public String longestPalindrome(String s) {
        if(s==null) return s;
        boolean[][] judge = new boolean[s.length()][s.length()];
        String res = "";
        for(int j=0; j<s.length(); j++) {
            for(int i=0; i<=j; i++) {
                judge[i][j] = s.charAt(i)==s.charAt(j) && ( j-i<=2 || judge[i+1][j-1] );
                if(judge[i][j] && j-i+1>res.length()) res = s.substring(i, j+1); 
            }
        }
        return res;
    }
}

中心扩散法：

class Solution {
    //time:O(n^2) space: O(1)
    String res = "";
    public String longestPalindrome(String s) {
        if(s==null) return s;
        for(int i=0; i<s.length(); i++) {
            helper(s, i, i);
            helper(s, i ,i+1);
        }
        return res;
    }
    
    public void helper(String s, int left, int right) {
        while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
            left--;
            right++;
        }
        if(s.substring(left+1, right).length()>res.length()) res=s.substring(left+1, right);
    }
}

参考：https://www.youtube.com/watch?v=m2Mk9JN5T4A