DP,O(KN)Time,java solution

  • -17

    I've got a DP solution.It can solved by O(kn).
    First,describe the struture of the optimum solution.We can use t[i][j] to indicate the max profit of j day which have happend i times transactions.
    We can recursively define the expression of t(i,j) like this:
    t[i][j]=max{ t[i][j-1], prices[j]-prices[j-1]+t[i-1][j-1]}.

    public class Solution {
    public int maxProfit(int k, int[] prices) {
       int n=prices.length;
       int[][] t=new int[k+1][n];
       for(int i=0;i<=k;i++){          
       for(int i=0;i<n;i++){
       for(int i=1;i<=k;i++){
          for(int j=1;j<n;j++){
       return t[k][n-1];


  • 0

    are you sure your code can pass all test cases?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.