Write the C code that solves the following problem with 1. Algorithm and 2.Algorithm.

Problem: For every number i = 1,2, .. n, a good i. The number P [i], which is the selling price for the day, is given. You can buy this product one day and sell it another day. After selling, you can buy the same product again on another day and sell it in the following days. You cannot buy a new product without selling it, that is, you cannot stock up. Your goal is to design an algorithm in C language that can get the maximum profit.

Example 1. Input => 7, 1, 5, 3, 6, 4 // of good i. sale prices for the day

Output => 7 // the maximum profit obtained in the output will be written.

Let the prices be 7, 1, 5, 3, 6, 4, respectively. The answer is 7 for this series. To get this, we buy for 1 lira on the 2nd day and sell for 5 lira on the 3rd day. Then on the 4th day we buy for 3 lira, on the 5th day we sell for 6 lira, and our profit becomes 5-1 + 6-3 = 7.

Example 2nd Input => 1, 2, 3, 4, 5

Output => 4

Let the prices be 1, 2, 3, 4, 5, respectively. The profit for this series is 4 lira, to get it, we buy 1 lira on day 1, we sell for 5 lira on day 5, the profit is 5-1 = 4 lira.

Example 3.Input => 7, 6, 4, 3, 1

Output => 0

Let the prices be 7, 6, 4, 3, 1, respectively. The profit for this series is 0 lira, the day we buy the goods, we cannot make a profit from the sale because the price on the other days will be smaller.

1.Algorithm:

(I will design this algorithm with the brute-force method, but I will do it in a way similar to the pseudo-code less-reduce-manage method.) Our main idea is very simple, let's assume that we get the goods for each day (i.day) in order, then Let's sell it for a higher price every day. Let's continue the same transaction in the days after the sale, calculate the profit and update our profit if this profit is more than our previous profit. Let me explain on Example1. Let profit = 0 initially. For i = 1, the price is 7. Let's get it at this price. If we look at other days, we cannot sell as prices are less than 7 and profit remains = 0. For i = 2, price = 1. Let's get it at this price. Let's try selling every day that we can make a profit. On the 3rd day, the price is 5 and the profit when we sell it = 5-1 = 4. Now, if we buy it for 3 liras on the 4th day, we can sell it on the 5th and 6th days. Since the total profit will be 4 + 6-3 = 7 if we sell on the 5th day, 4 + 4-3 = 5 if we sell on the 6th day, our new profit is 7. But the case i = 2 is not over. Now, let's sell the goods we bought on the 2nd day, the profit will be 3-1 = 2 on the 4th day, and then even if we buy this item on the 5th day, we cannot make a profit. In this case, the profit will not be updated since the total profit will be 2 Yet the i = 2 case is not over. If we sell the goods on the 2nd day, the profit will be = 6-1 = 5. However, since 5 <7, the profit will not be updated. For i = 2, the final situation is the sale of the good on Day 6, at which time the profit is 4-1 = 3 <7. In other words, if we buy the goods on the 2nd day, we will have a total profit of 7 lira. Then we continue the same process for i = 3, 4.5.

Now let's try to apply this algorithm a little smarter. Let s be our first day, and be our last day. (Initially b = 1, s = n, n is the size of the sequence P.) We i. day and satisfying the condition P [j]> P [i] j. we want to sell per day. Let us have a MaxPro (P, k, m) function where we can calculate the maximum profit in the range [k, m]. Naturally, MaxPro (P, k, m) = 0 if k> = m. In this case [b, s] in the interval i. take a day j. that we get from selling in a day

total profit = MaxPro (P, b, i-1) + P [j] -P [i] + MaxPro (P, j + 1, s].

Below is the pseudo code of the algorithm. The first call for this code is MaxPro (P, 1, n).

MaxPro (P, b, s)

if s<=b

then return 0

Pro0

for ib to s

for ji+1 to s

if P[j]>P[i]

then new_proP[j]-P[i]+MaxPro(P, b, i-1)+MaxPro(P, j+1, s)

if new_pro>Pro

then Pronew_pro

return Pro

Now let me explain this code again on Example1 (P = 7, 1, 5, 3, 6, 4). MaxPro (P, 1, n) has been called. So b = 1, s = n became. The first if condition is not met. Pro = 0. Loop i = 1, n started. For i = 1, j = 2, loop n starts, but since P [1] = 7, no condition P [j]> P [i] is satisfied for any j. For i = 2, j = 3, loop n begins. For j = 3 new_pro = P [3] -P [2] + MaxPro (P, 1, 1) + MaxPro(P, 4, 6) = 5-1 + 0 + MaxPro (P, 4, 6) = 4 + Becomes MaxPro (P, 4.6). To calculate this number, the code will call itself for b = 4, s = 6. Again, the first if condition is not met.

Inside this call, Pro = 0. The cycle i = 4, 6 begins. For i = 4, the loop j = 5, 6 begins. Since P [5]> P [4] for j = 5, new_kar = P [5] -P [4] + MaxPro (P, 4,

3) + MaxPro (P, 6,6) = 3. Profit = 3 because new_kar = 3> Pro = 0 in this call. For j = 6, new_pro = P [6] -P [4] + MaxPro (P, 4, 3) + MaxPro (P, 7, 6) = 1. Profit = 3, since new_profit = 1

2. Algorithm:

(This is actually a slightly smarter brute-force algorithm.) Let's think this way. If you were allowed to buy only once and sell only once, you would want to buy at the lowest price and sell at the highest price, so the largest of the positive differences P [j] - P [i], j> i, would be our maximum profit. (If none of these differences were positive, then profit = 0.) This would be max-min when the smallest element (min) of this array is to the left of the largest element (max). So if this situation exists, it would be sufficient to find max and min. Let's try to adapt this idea to our problem. For this, let's define the concepts of local minimum and local maximum. Actually, you know these concepts for functions. Let me explain on examples. For example, let's say 5,4,3,6,7,8,1,9. In this series, 3 and 1 are local minima. 5, 8 and 9 are local maximums. (If the next element from the first element is less than the first element, the first element is the local maximum, vice versa, the first element is the local minimum. If the element before the last element is less than the last element, the last element is the local maximum, otherwise the last element is the local minimum. If [i1]

P [i + 1], P [i] is the local maximum. If P [i-1]> P [i]

Our algorithm is as follows:

Get Pro = 0

Start with the first day and repeat the 3 steps below until all days are over

Find the first local minimum of the P series in the remaining days and plan to get it that day

Find the first local maximum of the P series in the next days and plan to sell it that day. (Do not import if the local maximum.)

Calculate the earnings from this shopping and add it to Pro.

Let me explain on all 3 examples. In Example1, the P sequence is 7, 1, 5, 3, 6, 4. The first local min = 1. We buy at this price. The first local maximum after this day is 5. We sell at this price. Profit = 4. The first local min = 3 after this day and the first local maximum is 6 on the following days. We earn 6-3 = 3 from this trade and our total profit = 4 + 3 = 7. Next local min = 4 but since there is no local maximum, we are not doing this.

In Example 2 the P sequence is 1,2,3,4,5. Local min = 1 and local maximum = 5 and 5-1 = 4 profit

In Example 3 there is no 7, 6, 4, 3, 1 first local minimum 1 and then local maximum, so we don't buy. Pro = 0 lags.

Since it is not very difficult to write the pseudo code of this algorithm, I leave it to you to write the pseudo code.