Maximum profits in stock

'''
 Logic: we used a dp table whose row denotes the number of transactions and column denotes the stocks prices daywise.
 so dp[i][j] is equal to maximum profit acheived till jth day after i transactions.

 using 0 transactions,no profit can be earned so 0th row will be filed with 0.
 using any number of transaction in one day only,no profit can be earned because stock
 price doesn't changing same day.

 for eg i=2 and j=5
 now,using i transactions,and at jth day,maxium profit will be:
 either do i transaaction till j-1th day ie. dp[i][j-1]
 or do i-1 transaction till day 0 and  last transaction or ith transaction between day 0 to jth day ie. dp[1][0]+arr[5]-arr[0]
 or do i-1 transaction till day 1 and last transaction or ith transaction between day 1 to jth day  ie. dp[1][1]+arr[5]-arr[1]
 .                                                                                                  ie. dp[1][2]+arr[5]-arr[2]
 .
 .
 or do i-1th transaction till j-1 day and last transaction or ith transaction between day j-1 to jth day ie. dp[1][4]+arr[5]-arr[4]
 so,arr[5] is common in above example ie. stock price of current day
 so max_val will store the value of maximum profit of i-1th transaction - stock price at that day so if we will add
 the stock price of jth day then we will have maximum of last transaction completed on jth day.

Maximum profit obtained till the jth day using at most i transactions.less than i transaction is also possible but each transaction means buy+sell both.

'''
class Solution:
    def maxProfit(self, k, n, arr):
        dp = [[0] * 501 for _ in range(201)] #Maximum profit obtained till the jth day using at most i transactions.

        for i in range(1, k + 1):
            max_val = float('-inf')

            for j in range(1, n):
                # update max_val if profit till last transaction - that day price
                max_val = max(max_val, dp[i - 1][j - 1] - arr[j - 1])

                # check if selling today gives better profit, max_val+buying price of today & dp[i][j-1] don't do any transaction at all
                dp[i][j] = max(max_val + arr[j], dp[i][j - 1])

        return dp[k][n - 1]