贪心或者dp

设当前天为为i，那么在i天，我们可以买或者不买，买的话应该用prices[i] - min(prices[j]) 0 <= j < i

import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int n = prices.length;
        int a = 0;
        int b = 1000000;
        for(int i = 0;i < n;i++){
            a = Math.max(a,prices[i] - b);
            b = Math.min(b,prices[i]);
        }
        return a;
    }
}

dp:设f[i][2]：为[0,i]所能买卖股票的集合，0为买入，1为卖出
f[i][0] = min(f[i - 1][0],prices[i])
f[i][1] = max(f[i - 1][1],prices[i] - f[i - 1][0])

import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int n = prices.length;
        int f[][] = new int[n + 10][2];
        f[0][0] = 1000000;
        f[0][1] = 0;
        for(int i = 0;i < n;i++){
            //为了防止下标越界，将i统一+1即可
            f[i + 1][0] = Math.min(f[i][0],prices[i]);
            f[i + 1][1] = Math.max(f[i][1],prices[i] - f[i][0]);
        }
        return f[n][1];
    }
}