Pranay Chandra because the looping var isn't reset within the loop. Each element in the index is still only looked at most once, so still O(n). The while loops just keep the index variable within bounds.
Using size of(arr)/ size of(arr[0]) is not advised inside another function, when array is passed as parameter. Otherwise, it is fine. Check out here: www.geeksforgeeks.org/using-sizof-operator-with-array-paratmeters/
They are just saying not to use that method in another function because if you pass array to a function then we doesn't pass the whole array to the function ,we just pass the base address to a pointer . So in that case instead of getting array size you will get the pointer size(which receive the base address) and that will give you an incorrect answer.(except for the case when pointer size and array size is similar)
its right trace properly ,it means if current price is more than next one then iterate otherwise stop and it is minima .as much as what i have understood
Here in this code, you have meesed up both 2 if conditions. TO find the local minima, the current element should be smaller than the next element.But you wrote (if(iprice[i+1])..where it should be (if(i
In the "Interval" structure instance "sol", why has it been declared to have (n/2+1) elements? shouldn't just (n/2) suffice as buy and sell are always in pairs?
Sir, even when the "n" is odd (like in the given example as well), it shouldn't matter, the code will still work with n/2 instances of "Interval" structure.
@@GeeksforGeeksVideos why not just do this : def max_profit_smart(arr): profit = 0 for i in range(0, len(arr) - 1): if arr[i + 1] > arr[i]: profit += arr[i + 1] - arr[i] // sum of a[i+1] - a[i] as 0
Complicated the question way too much while implementation just sell the stock whenever it goes up and subtract the previous minima to get the maximum profit class Solution { public int maxProfit(int[] prices) { int min = 0,profit=0; for(int i:prices){ if(min
The logic is to sell stock if the prices are falling next day. Then buy again next day and keep doing the same procedure. So if there is no local Maxima, max profit would be 0.
I dont know why no one is pointing.. this program is wrong.. lets take this arr = {2,16,15,30,8,25,80}; local minima = 2 | 15 | 8 | local maxima = 16 | 30 | 80 | max diff out of 14, 15 and 72 is 72..coming as my max profit. but if i buy at 2 and sell at 30 then buy at 8 and sell at 80.. max profit will be 100.
(310 - 100) + (695 - 140) = 765 Maybe you are confusing it with another problem - where it is allowed to only buy and sell once. Here you can buy and sell the stock any no. of times.
How about iterating backwards? I could solve it with just one loop. public class Solution { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int size = scanner.nextInt(); for (int i = 0; i < size; i++) { int numOfDays = scanner.nextInt(); int[] prices = new int[numOfDays]; for (int j = 0; j < numOfDays; j++) { prices[j] = scanner.nextInt(); } System.out.println(getMaxProfit(prices)); } } public static long getMaxProfit(int[] prices) { long profit = 0L; int maxSoFar = 0; for (int i = prices.length - 1; i > -1 ; i--) { if (prices[i] >= maxSoFar) { maxSoFar = prices[i]; } profit += maxSoFar - prices[i]; } return profit; } }
which algorithm did u use?
how come the TC be o(n) if you are using while inside another while ?
Pranay Chandra because the looping var isn't reset within the loop. Each element in the index is still only looked at most once, so still O(n). The while loops just keep the index variable within bounds.
Could you tell which type of approach is this algorithm?
greedy algorithm.. as we are trying to make an optimal decision using local values i.e. not taking into account the whole data or global values
Excellent Explanation!♥
well explained!
Well Explained !!
i think here at least 3 elements needed to make the profit...
why are we not selling on day 5? for max profit
one of the geeks article says that size of(arr)/ size of(arr[0]) will not provide no.of elements in that array but you people only using that logic.
Using size of(arr)/ size of(arr[0]) is not advised inside another function, when array is passed as parameter. Otherwise, it is fine. Check out here: www.geeksforgeeks.org/using-sizof-operator-with-array-paratmeters/
They are just saying not to use that method in another function because if you pass array to a function then we doesn't
pass the whole array to the function ,we just pass the base address to a pointer . So in that case instead of getting array size you will get the pointer size(which receive the base address) and that will give you an incorrect answer.(except for the case when pointer size and array size is similar)
Awesome explaination
Nice name :)
Thanks!
Thanks
minima condition is wrong price[i]
its right trace properly ,it means if current price is more than next one then iterate otherwise stop and it is minima .as much as what i have understood
while(i=price[i])
break;
else i++;
}
for your case we have to do like this
Here in this code, you have meesed up both 2 if conditions. TO find the local minima, the current element should be smaller than the next element.But you wrote (if(iprice[i+1])..where it should be (if(i
// Find Local Minima. Note that the limit is (n-2) as we are
// comparing present element to the next element.
while ((i < n-1) && (price[i+1]
he has explained in one way, and done the code in the other...you stick to the one you want
good video.
In the "Interval" structure instance "sol", why has it been declared to have (n/2+1) elements? shouldn't just (n/2) suffice as buy and sell are always in pairs?
Buy and Sell are paired into one structure, yes. But, n represents the number of days which maybe odd. Hence, n/2+1.
Sir, even when the "n" is odd (like in the given example as well), it shouldn't matter, the code will still work with n/2 instances of "Interval" structure.
@@GeeksforGeeksVideos why not just do this :
def max_profit_smart(arr):
profit = 0
for i in range(0, len(arr) - 1):
if arr[i + 1] > arr[i]:
profit += arr[i + 1] - arr[i]
// sum of a[i+1] - a[i] as 0
@@MassiveAchievement comments in python are written with # not //😜
@@a.yashwanth I know, but I don't care
Using python is legal too...constitution still allows it
Yup, feel the pain for python users trying to learn dsa. Every other explanation is in either Java or Cpp
it's literally just a loop, no matter what language he uses, it's the same logic
Complicated the question way too much while implementation
just sell the stock whenever it goes up and subtract the previous minima to get the maximum profit
class Solution {
public int maxProfit(int[] prices) {
int min = 0,profit=0;
for(int i:prices){
if(min
very helping.
night ppl
The logic is to sell stock if the prices are falling next day. Then buy again next day and keep doing the same procedure. So if there is no local Maxima, max profit would be 0.
k
How it will for {10, 22, 5, 75, 65, 80}
Here
local Minima | 10 | 5 | 65 |
Local Maxima | 22 | 75 | 80 |
Now how to choose two pairs?
We don't have to choose two pairs. We just have to find maximum profit. In this case max profit would be = (22-10) + (75-5) + (80-65)
@@vipulsingh4637 if we are asked to find just 2(as a constraint) , then sort each on basis of profit and pick the maximum too :)
@@nitinrathee7077 yeah. But that takes nlogn
@@a.yashwanth take two variables max1 and max2 if you want to avoid sorting
@@nitinrathee7077 [7,1,5,3,6,4] for 1 it should be 5 not 4
I dont know why no one is pointing.. this program is wrong..
lets take this arr = {2,16,15,30,8,25,80};
local minima = 2 | 15 | 8 |
local maxima = 16 | 30 | 80 |
max diff out of 14, 15 and 72 is 72..coming as my max profit.
but if i buy at 2 and sell at 30 then buy at 8 and sell at 80.. max profit will be 100.
14+15+72=101 and according to your strategy its 100
net profit is to be maximized, not a particular profit...
if the number of transactions are given and there exists n number of local maxima and minima then??????????????
How come there are n maximas and minimas.
this is just wrong. try 140 instead of 40. {100, 180, 260, 310, 140, 535, 695} - obviously the best strategy is to buy on day 0 and sell on last day.
(310 - 100) + (695 - 140) = 765
Maybe you are confusing it with another problem - where it is allowed to only buy and sell once. Here you can buy and sell the stock any no. of times.
i think you are right, but then this is just trivial. this problem becomes challenging only when you are allowed to buy and sell once.
Then it is very easy, you just need to find the maximum and minimum.
What if the max appears before the min? like {600 180 450 220}
@@soumik76 buy on 2nd day and sell on 3rd day
WTF! YOU ARE TYPING WHILE SAYING VERY IRRITATING NOICE...
This Solution is wrong for the input {1,2,3,4,5}.
Profit: 5-1=4 which is maximum.Solution is right.
stop explanation
very flawed video
poor explanation
How about iterating backwards?
I could solve it with just one loop.
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
for (int i = 0; i < size; i++) {
int numOfDays = scanner.nextInt();
int[] prices = new int[numOfDays];
for (int j = 0; j < numOfDays; j++) {
prices[j] = scanner.nextInt();
}
System.out.println(getMaxProfit(prices));
}
}
public static long getMaxProfit(int[] prices) {
long profit = 0L;
int maxSoFar = 0;
for (int i = prices.length - 1; i > -1 ; i--) {
if (prices[i] >= maxSoFar) {
maxSoFar = prices[i];
}
profit += maxSoFar - prices[i];
}
return profit;
}
}
very well explained!
🤩