Please also provide proof of time complexity and correctness.

Problem 4: (30 points) Your friends have been studying the closing prices of tech stocks, looking for interesting patterns. They've defined something called a rising trend, as follows. They have the closing price for a given stock recorded for n days in succession; let these prices be denoted P[1], P[2],... , P[n]. A rising trend in these prices is a subsequence of the prices Pll, Pli2], . . . ,PRk], for days i122