We are given a array of price predictions for m stocks for n consecutive days. The price of stock i for day j is A[i][j] for i = 1, . . . , m and j = 1, . . . , n. You are tasked with finding the maximum possible profit by buying and selling stocks. The predicted price at any day will always be a non-negative integer. You can hold only one share of one stock at a time. You are allowed to buy a stock on the same day you sell another stock.
Problem: Given a matrix A of m × n integers (non-negative) representing the predicted prices of m stocks for n days and an integer k (positive), find a sequence of at most k transactions that gives maximum profit. [Hint :- Try to solve for k = 2 first and then expand that solution.]
Design a Θ(m ∗ n 2 ∗ k) time dynamic programming algorithm for solving above Problem
Design a Θ(m ∗ n ∗ k) time dynamic programming algorithm for solving above Problem
