-
Notifications
You must be signed in to change notification settings - Fork 0
/
ques 7.txt
110 lines (71 loc) · 2.43 KB
/
ques 7.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
MCA 301 : Design and analysis of Algorithms
Assignment : 3
Promlem statement : 7
--------------------
Programming Approach
--------------------
1. Dynamic Programming
2. Iterative
-----------
EXPLANATION
-----------
Global variables
----------------
int buy[N] to store the min price value seen so far at each day denoted by 'i'
int p[N]={9,1,5} price per share at each day 'i'
int k loop counter variable
int profit[N] stores profit calculated at each day
======================================================================================================================
--------------------------------------
Function 1: minBuyday()
--------------------------------------
**********
Pseudocode
**********
minBuyday()
1. buy[0] = p[0] , initialise with price of shares at first day;
2. for i = 1 to N-1
3. buy[k]=min(buy[k-1],p[k])
4. return (index of the day when buying is min)
DOCUMENTATION :
/*
Objective : To find min value day seen so far .
Input : None
Return : Min day to buy shares
*/
======================================================================================================================
-------------------------
Function 2: profit_day()
-------------------------
**********
Pseudocode
**********
profit_day():
1. profit[0]=0; //if sold first day only , not a possible case
2. for k=1 to N-1
3. //recurssive
profit[k]=max{(profit[k-1],(p[k]-buy[k]))
4. return (max profit , day at which selling share will yeild max profit)
DOCUMENTATION:
/*
Objective : To compute profit at each day by selling shares .
Input : None
Return : Max Profit per share and day to sell shares-(as a pair)
*/
======================================================================================================================
----------
Complexity
----------
Function 1:
line 1 -> O(1)
loop 2-3 -> O(n) linear time
line 4 -> O(1)
--------------------------------------------------
Function 2:
line 1 -> O(1)
line 2-3 -> O(n)
line 4 -> O(1)
--------------------------------------------------
Time complexity = O(n)+O(n)
=O(n) //more efficient approach
Space complexity = O(n^2) //profit array and buy array , each of size N