题目描述

假设你有一个数组，其中第\ i i 个元素是股票在第\ i i 天的价格。
你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。

示例1

输入
[1,4,2]
返回值
3

思路

1. 这种有点像双指针的问题，使用以下dp模板：一维数组，i往右遍历，j从i开始向左遍历。
2. code1中状态转移方程为dp[i] = Math.max(dp[i-1],prices[i]-prices[j])。然而是错误的，测试后只过了一半左右。经过调试后发现，在j循环中，计算的前一个dp[i]会被覆盖，因此在code2中又加了一个max函数。当然code3中不用数组也就不存在该问题。
3. 该问题也可以不用dp做，这里是为了练习dp。

code1(有误)

import java.util.*;
public class Solution {
    public int maxProfit (int[] prices) {
        if(prices==null || prices.length==0)return 0;
        int n = prices.length;
        int[] dp = new int[n];
        int max=0;
        for(int i=1;i<n;i++)
            for(int j=i-1;j>=0;j--)
                dp[i] = Math.max(dp[i-1],prices[i]-prices[j]);    
        System.out.println(Arrays.toString(dp));
        return dp[n-1];
    }
}

code2(ac)

import java.util.*;
public class Solution {
    public int maxProfit (int[] prices) {
        if(prices==null || prices.length==0)return 0;
        int n = prices.length;
        int[] dp = new int[n];
        int max=0;
        for(int i=1;i<n;i++){
            for(int j=i-1;j>=0;j--)
                dp[i] = Math.max(dp[i],Math.max(dp[i-1],prices[i]-prices[j])); // different
        System.out.println(Arrays.toString(dp));
        return dp[n-1];
    }
}

code3(ac)

import java.util.*;
public class Solution {
    public int maxProfit (int[] prices) {
        if(prices==null || prices.length==0)return 0;
        int n = prices.length;
        int dp = 0;
        int max=0;
        for(int i=1;i<n;i++)
            for(int j=i-1;j>=0;j--)
                dp = Math.max(dp,prices[i]-prices[j]); // different   
        return dp;
    }
}