DP,O(KN)Time,java solution


  • -17
    M

    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++){          
          t[k][0]=0;
       }
       for(int i=0;i<n;i++){
          t[0][i]=0;
       }
       for(int i=1;i<=k;i++){
          for(int j=1;j<n;j++){
              t[i][j]=Math.max(t[i][j-1],prices[j]-prices[j-1]+t[i-1][j-1]);
          }
       }
       return t[k][n-1];
    }
    

    }


  • 0
    B

    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.