### Problem Statement

Say you have an array for which the

*i*th element is the price of a given stock on day*i*.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

**Link to GitHub**:Code**Example**

**1**

Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger

```
than buying price)
```

**Example 2**

Input: [7, 6, 4, 3, 1] Output: 0 In this case, no transaction is done, i.e. max profit = 0

###

**Solution
**

- We need 2 variables maxcur and maxsoFar.
- maxCur keeps on adding 2 consecutive stock price
- maxCur would then compare value with maxsoFar.
- When we reach end of the array we would get maxsoFar

public static int get(int [] prices){ int maxSoFar=0, maxCur=0; //We need to start getting the difference from the second and

//first element in the array and // keep incrementing i for(int i=1;i<=prices.length-1;i++) { //gets the current max maxCur=Math.max(0, maxCur+=prices[i]-prices[i-1]); //gets the max so far maxSoFar=Math.max(maxCur, maxSoFar); } return maxSoFar; }

### Iteration

**IMPLEMENTATION IN PYTHON**

Time Complexity O(n)^2 Space Complexity 0(1)

stocks=[7,1,5,2,4] def buy_sell_once(s): maxprofit=0 #first loop for i in range(len(s)-1): for j in range(i+1,len(s)): if s[j] - s[i] > maxprofit: maxprofit=s[j] - s[i] return maxprofit m=buy_sell_once(stocks) print(m)

Time Complexity O(n) Space Complexity 0(1)

1 2 3 4 5 6 7 8 9 10 11 12 | stocks =[7,1,5,2,4] def buy_sell_once_ef(s): max_profit=0 min_price=stocks[0] for price in range(len(stocks)-1): min_price = min(min_price,price) profit =(price-min_price) max_profit=max(profit,max_profit) return max_profit m=buy_sell_once(stocks) print(m) |

Link to github : BuySellStock

## No comments:

## Post a Comment