Thank you bhaiya ❤❤. Aj ka problem ka solution soch hi nhi paa rha tha. Sorting and sliding window type ka aya tha dimag me. H/W: class Solution { public: int maxScoreSightseeingPair(vector& values) { int n = values.size(); priority_queue pq; pq.push(values[0]);
brute force aane lga dimag me (logic) and linkedlist me maja aa rha karne me bhaiya node node khel rha aapki vedio bhut helpful hai thanks you !!🥰🥰🥰🥰🥰🥰
Thank you bhaiya. Here is my solution for HW: class Solution { public int maxScoreSightseeingPair(int[] values) { // Using priority queue to store maximum value of values[i] + i till i-th index PriorityQueue pq = new PriorityQueue((a,b) -> b - a); pq.offer(values[0] + 0); // 0 for completeness int maxScore = values[0];
for(int j = 1; j < values.length; ++j) { maxScore = Math.max(maxScore, pq.peek() + values[j] - j); pq.offer(values[j] + j); // add current to the top } return maxScore; } }
using max heap class Solution { public: int maxScoreSightseeingPair(vector& values) { int n = values.size(); priority_queue pq; pq.push(values[0]); int res=INT_MIN; for (int j = 1; j < n; j++) { res=max(res,pq.top()+values[j]-j); pq.push(values[j] + j); } return res; } };
Sir I am followed your playlist , currently start array playlist. Progress Easy :1 Medium :3 Hard :2 Just start from yesterday I promise I will not take a break until got good job in big MNCS❤🎉
Only after watching the equation tip I was able to solve the question. Thank you bhaiya 😄 class Solution { public int maxScoreSightseeingPair(int[] values) { PriorityQueue pq = new PriorityQueue((a, b) -> (a[0] != b[0]) ? b[0] - a[0] : b[1] - a[1]); int result = Integer.MIN_VALUE; for(int i=0; i
Hi MIK, really appreciate your hardwork and these videos you make on POTD, I am currently in 2nd year of college and decided to do the leetcode potd in the vacations from dussehra and diwali and have done quite a few of them , took help from your videos whenever needed and they have really helped a lot. Due to these videos I was able to solve today's problem in the exact same manner as you did, I managed to do the same optimisation, the difference being I kept track of j-score while traversing in reverse direction and updated the j-score and total score at every index from n-2 to 0, it was a very good feeling , I realised that the work I have put in actually has improved my skills, a ton of thanks to you :) Also I am done with the major DSA topics, graph and DP are left, so can I follow your playlists if I want to do these topics from scratch? Thanks a lot anyway
Definitely ❤️ And great work. 👌👌 Always remember, for any topic 1) First study it’s concepts 2) Then solve Qns I usually create two playlists for every topic : 1) Concepts Playlist - Contains from basic concepts to expert concepts. 2) Popular Interview Problems playlist. I have created concepts and interview problems playlist for 1) Graph 2) Recursion 3) DP 4) Segment Tree Planning soon to create concepts playlist for Tree as well. Graph Concepts - ruclips.net/p/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY&si=lZG2IJTmSW4kRrx- Graph Popular Interview Problems - ruclips.net/p/PLpIkg8OmuX-I_49pdy1XFY6OcATnxUrrO&si=CG2JvGWVmvoSqvWA Recursion Concepts - ruclips.net/p/PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM&si=614iI4NyHY-FTeJH Recursion Problems (In progress) - ruclips.net/p/PLpIkg8OmuX-IXOgDP_YYiJFqfCFKFBDkO&si=88fBhRnr62OYTnDP DP Concepts (In progress) - ruclips.net/p/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt&si=laFVYy6ep2BkOg0s DP Popular interview problems - ruclips.net/p/PLpIkg8OmuX-L_QqcKB5abYynQbonaNcq3&si=VHEn9b-wqTnAVyyi Segment Tree Concepts - ruclips.net/p/PLpIkg8OmuX-K1qUIQToCllUO0UIKXt8dB&si=xm7DqRN4H0eZwna4
@@codestorywithMIK Thanks a lot sir, BTW I have a suggestion, you can start covering the questions asked in real OAs and interviews these days, as even for my batch we will be having intern season at the start of summer in 2025, so we will get a good idea of the kind of variations we may face from standard LC problems. Also you are an SDE 3 so possibly you are taking interviews at your company, so what can be the good projects to showcase and general tips. Thanks again, hope the channel grows to new heights :)
Using PriorityQueue: class Solution { public int maxScoreSightseeingPair(int[] values) { int n=values.length; PriorityQueuepq=new PriorityQueue(Comparator.reverseOrder()); pq.add(values[0]); int ans=Integer.MIN_VALUE; for(int i=1;i
Priority queue implementation homework done ✅ class Solution { public: int maxScoreSightseeingPair(vector& values) { int n=values.size(); int ans=0; priority_queuepq; pq.push(values[0]); int pair_i=values[0]+0; for(int i=1;i
Able to code on myself @10:04 class Solution { public: int maxScoreSightseeingPair(vector& values) { int ans = 0, maxi = values[0]; for(int j = 1; j < values.size(); j++) { ans = max(ans, values[j] + maxi - j); maxi = max(maxi, values[j] + j); } return ans; } }; I know, it took me a time to get to the approach to such a easy question.
priority queue: class Solution { public: int maxScoreSightseeingPair(vector& values) { int maxscore = INT_MIN; int n = values.size()-1; priority_queue pq; pq.push(values[0]); for(int i = 1;i
sir min heap solution :- class Solution { public: int maxScoreSightseeingPair(vector& values) { int n = values.size(); priority_queuepq; int result = INT_MIN; for(int j=1;j
//priority queue approach class Solution { public: int maxScoreSightseeingPair(vector& values) { int n=values.size(); priority_queue pq; int res=0; pq.push(values[0]); for(int i=1;i
Using PQ, class Solution { public int maxScoreSightseeingPair(int[] values) { int result = 0; int n = values.length; PriorityQueue pq = new PriorityQueue((a, b) -> (b-a));
class Solution { public: int maxScoreSightseeingPair(vector& values) { priority_queuepq; pq.push(values[0]); int ans = INT_MIN; for(int i = 1; i < values.size(); i++){ int value = pq.top() + values[i] - i; ans = max(ans, value); pq.push(values[i] + i); } return ans; } }; Homework Done !!
Single Traversal O(N) Time & O(1) Space Solution class Solution { public: int maxScoreSightseeingPair(vector& values) { int n = values.size(); int ans = -1e9; int maxi = values[n-1] - n + 1; for(int i=n-2;i>=0;i--){ ans=max(ans,values[i]+i+maxi); maxi=max(maxi,values[i]-i); } return ans; } };
class Solution { public: int maxScoreSightseeingPair(vector& values) { int n = values.size(); int ans = INT_MIN; priority_queue pq; pq.push(values[0]); for (int i = 1; i < n; i++) { ans = max(ans, pq.top() + values[i] - i); pq.push(values[i] + i); } return ans; } };
class Solution { public: int maxScoreSightseeingPair(vector& values) { int n = values.size(); priority_queue pq; pq.push(values[0]); int result = 0; for(int j = 1; j < n; j++) { int x = values[j] - j; int y = pq.top(); result = max(result, x + y); pq.push(values[j] + j); } return result; } };
Always study the concepts first. Then move to Qns. DP Concepts playlist - ruclips.net/p/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt&si=j4OPlfm8SFzxvsW2 Hope this helps ❤️🙏
Using Priority Queue: class Solution { public: int maxScoreSightseeingPair(vector& values) { int n=values.size(); int ans=INT_MIN; priority_queuepq; for(int j=1;j
class Solution { public int maxScoreSightseeingPair(int[] values) { int n=values.length; for(int i=0;i=0;i--){ temp[i]=Math.max(values[i+1],temp[i+1]); } for(int i=0;i
Best Solution :-> O(1) Space complexity and O(n) time complexity class Solution { public int maxScoreSightseeingPair(int[] values) { int n=values.length; int ans=-(int)(1e6); int max=values[0]; for(int i=1;i
class Solution { public int maxScoreSightseeingPair(int[] values) { PriorityQueue pq = new PriorityQueue(Collections.reverseOrder()); int max =0; for(int i=1;i
Using Priority Queue C++: class Solution { public: int maxScoreSightseeingPair(vector& values) { int n = values.size(); int ans = INT_MIN; priority_queuepq; pq.push(values[0]); int i = 0; for(int j=1;j
class Solution { public int maxScoreSightseeingPair(int[] values) { int n = values.length; PriorityQueue pq = new PriorityQueue((a, b) -> b[0] - a[0]); for(int i=0;i0;j--) { while(pq.peek()[1] >= j) pq.poll(); max = Math.max(max, pq.peek()[0] + values[j] - j); } return max; } } // rearranging equation to {(values[i] + i) + (values[j] - j)} where: i < j // removing elmts from pq based on value takes log(n) time, while removing top elmt takes O(1) time
PriorityQueue using java class Solution { public int maxScoreSightseeingPair(int[] values) { int n = values.length; int max = 0; int maxLeft = 0; PriorityQueue maxheap = new PriorityQueue(Collections.reverseOrder()); maxheap.add(values[0]); for(int i=1;i values[i] + i + values[j] - j;. we need to maximize the values[i] + i
/* Using Priority Queue ---> Homework done */ class Solution { public int maxScoreSightseeingPair(int[] a) { int n = a.length; int res = -(int)1e9; PriorityQueue q = new PriorityQueue(Comparator.reverseOrder()); q.add(a[0]); for(int j = 1; j < n; j++){ res = Math.max(res, (a[j] - j + q.peek())); int val = a[j] + j; q.add(val); } return res; } }
PriorityQueue Solution in Java class Solution { public int maxScoreSightseeingPair(int[] values) { PriorityQueue pq = new PriorityQueue((a, b) -> Integer.compare(b, a)); int max = 0; pq.add(values[0]); for(int i=1;i< values.length;i++){ max = Math.max(max,values[i]-i+ pq.peek()); pq.add(values[i]+i); } System.out.println(pq); return max; } }
@@xyzb717 the logic behind that line was if you reach the end of the array and you still need to select some element (ie, count != 0) then this case is invalid and inorder to ignore this case i return a very small value (-1e9) so that this case does not effect my final answer as in the last line we choose the maximum value from both the cases ie, return dp[i][count] = max(take, not_take); so by returning a very small value i ensure that the invalid case is never chosen
this question also solve by kadane algo aap ka algo me ek vector extra hain joki usko bhi reduce kar sakte hain direct ek extra variable le kar jo previous ka max rakhe ga but aap ke liye 🥰 class Solution { public: int maxScoreSightseeingPair(vector& values) { int sum =0; int pre =values[0]; for(int j=1;j
def f(ar,i,k,m): if i>=len(ar): if k==0: return 0 else : return 0 if (i,k) in m: return m[(i,k)] np=0 p=0 np=0+f(ar,i+1,k,m) for j in range (i+1,len(ar)): p=max(p,ar[i]+i+ar[j]-j) f(ar,i+1,k-1,m) m[(i,k)]=max(p,np) return m[(i,k)] See i have this by Dinamic programming not that much optimize but works
Done using priority queue class Solution { public: // using pq int maxScoreSightseeingPair(vector& values) { int n=values.size(); priority_queuepq; pq.push(0+values[0]); int ans=INT_MIN; for(int i=1;i
took the equation hint then self solved: int maxScoreSightseeingPair(vector& values) { int sz = values.size(), ans=0; vector a(values.begin(), values.end()); transform(a.begin(), a.end(), a.begin(), [i=0](int n) mutable { return n + i++;}); for(int i=1; i
class Solution { public: int maxScoreSightseeingPair(vector& values) { int n = values.size(); priority_queuepq; pq.push(values[0]); int res = 0; for(int j=1;j
motivation level harder, 🎉❤
Thank you bhaiya ❤❤. Aj ka problem ka solution soch hi nhi paa rha tha. Sorting and sliding window type ka aya tha dimag me.
H/W:
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
priority_queue pq;
pq.push(values[0]);
int result = -1;
for(int j=1; j
I will complete 15 questions of stacks before the end of this year.... from your playlist
Let’s go 🔥
me too
brute force aane lga dimag me (logic) and linkedlist me maja aa rha karne me bhaiya node node khel rha aapki vedio bhut helpful hai thanks you !!🥰🥰🥰🥰🥰🥰
Explanation top notch 💯 Able to code optimally after seeing first 10 minutes ❤
yup, first 10 minutes are enough.
Thank you bhaiya. Here is my solution for HW:
class Solution {
public int maxScoreSightseeingPair(int[] values) {
// Using priority queue to store maximum value of values[i] + i till i-th index
PriorityQueue pq = new PriorityQueue((a,b) -> b - a);
pq.offer(values[0] + 0); // 0 for completeness
int maxScore = values[0];
for(int j = 1; j < values.length; ++j) {
maxScore = Math.max(maxScore, pq.peek() + values[j] - j);
pq.offer(values[j] + j); // add current to the top
}
return maxScore;
}
}
using max heap
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
priority_queue pq;
pq.push(values[0]);
int res=INT_MIN;
for (int j = 1; j < n; j++) {
res=max(res,pq.top()+values[j]-j);
pq.push(values[j] + j);
}
return res;
}
};
You are just real hero for uss❤❤ your channel will reach millions ,billions and many more soon✌️✌️🎉🎉
int maxScoreSightseeingPair(vector& values) {
priority_queuepq;
pq.push(values[0]);
int result = INT_MIN;
for(int i = 1 ; i < values.size();i++){
result = max(result , (values[i] - i) + pq.top()) ;
pq.push(values[i] + i);
}
return result;
}
thank you bhaiya , aaj thoda confidence aur mila ❤❤❤
no need to use PQ
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int ans = 0, maxi = values[0];
for(int j = 1; j < values.size(); j++) {
ans = max(ans, values[j] + maxi - j);
maxi = max(maxi, values[j] + j);
}
return ans;
}
};
@@rushabhlegion2560 best soluttion bro 👍
@@rushabhlegion2560 vedio dekh le bhai. bhaiya ne bola hai islie log post kar rhe hai
👍👍
Wow, thank you. It's clear and seems very easy now
One ❤ for bhaiya ji for daily uploading a video
Sir I am followed your playlist , currently start array playlist.
Progress
Easy :1
Medium :3
Hard :2
Just start from yesterday I promise I will not take a break until got good job in big MNCS❤🎉
Bhai saath mai solve kare kya if you wish?
Thank so much bayya 😊😊😊❤❤
thankyou sir very good approach
solved this on my own 😄😄
Motivation ❤❤❤❤❤
Thank you so much bhaiyya, will upsolve with max heap..
Only after watching the equation tip I was able to solve the question. Thank you bhaiya 😄
class Solution {
public int maxScoreSightseeingPair(int[] values) {
PriorityQueue pq = new PriorityQueue((a, b) -> (a[0] != b[0]) ? b[0] - a[0] : b[1] - a[1]);
int result = Integer.MIN_VALUE;
for(int i=0; i
jab meri job mnc me lgegi to aapse jaroor milooga love you bhut sara bhaiya 🤩🤩🤩🤭🤭
Radhe Radhe ❤❤❤
Hi MIK, really appreciate your hardwork and these videos you make on POTD, I am currently in 2nd year of college and decided to do the leetcode potd in the vacations from dussehra and diwali and have done quite a few of them , took help from your videos whenever needed and they have really helped a lot. Due to these videos I was able to solve today's problem in the exact same manner as you did, I managed to do the same optimisation, the difference being I kept track of j-score while traversing in reverse direction and updated the j-score and total score at every index from n-2 to 0, it was a very good feeling , I realised that the work I have put in actually has improved my skills, a ton of thanks to you :) Also I am done with the major DSA topics, graph and DP are left, so can I follow your playlists if I want to do these topics from scratch? Thanks a lot anyway
Definitely ❤️
And great work. 👌👌
Always remember, for any topic
1) First study it’s concepts
2) Then solve Qns
I usually create two playlists for every topic :
1) Concepts Playlist - Contains from basic concepts to expert concepts.
2) Popular Interview Problems playlist.
I have created concepts and interview problems playlist for
1) Graph
2) Recursion
3) DP
4) Segment Tree
Planning soon to create concepts playlist for Tree as well.
Graph Concepts - ruclips.net/p/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY&si=lZG2IJTmSW4kRrx-
Graph Popular Interview Problems - ruclips.net/p/PLpIkg8OmuX-I_49pdy1XFY6OcATnxUrrO&si=CG2JvGWVmvoSqvWA
Recursion Concepts - ruclips.net/p/PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM&si=614iI4NyHY-FTeJH
Recursion Problems (In progress) - ruclips.net/p/PLpIkg8OmuX-IXOgDP_YYiJFqfCFKFBDkO&si=88fBhRnr62OYTnDP
DP Concepts (In progress) - ruclips.net/p/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt&si=laFVYy6ep2BkOg0s
DP Popular interview problems - ruclips.net/p/PLpIkg8OmuX-L_QqcKB5abYynQbonaNcq3&si=VHEn9b-wqTnAVyyi
Segment Tree Concepts -
ruclips.net/p/PLpIkg8OmuX-K1qUIQToCllUO0UIKXt8dB&si=xm7DqRN4H0eZwna4
@@codestorywithMIK Thanks a lot sir, BTW I have a suggestion, you can start covering the questions asked in real OAs and interviews these days, as even for my batch we will be having intern season at the start of summer in 2025, so we will get a good idea of the kind of variations we may face from standard LC problems. Also you are an SDE 3 so possibly you are taking interviews at your company, so what can be the good projects to showcase and general tips. Thanks again, hope the channel grows to new heights :)
Using PriorityQueue:
class Solution {
public int maxScoreSightseeingPair(int[] values) {
int n=values.length;
PriorityQueuepq=new PriorityQueue(Comparator.reverseOrder());
pq.add(values[0]);
int ans=Integer.MIN_VALUE;
for(int i=1;i
Legend is here 🤩
On time sir
home work done........
olass Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
int result =0;
priority_queuepq;
pq.push( values[0] + 0);
for(int j = 1; j
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
int maxi = values[0];
int ans = 0;
for(int i=1;i
Priority Queue Solution
int maxScoreSightseeingPair(vector& values) {
priority_queue pq;
pq.push(values[0]);
int maxScore = 0;
for(int i = 1; i < values.size(); i++){
maxScore = max(maxScore,pq.top()+(values[i]-i));
pq.push(values[i]+i);
}
return maxScore;
}
Priority queue implementation homework done ✅
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int n=values.size();
int ans=0;
priority_queuepq;
pq.push(values[0]);
int pair_i=values[0]+0;
for(int i=1;i
Priority Queue Solution:-
class Solution {
public:
int maxScoreSightseeingPair(vector& nums) {
int n = nums.size();
priority_queue pq;
int score = INT_MIN;
for(int i = 0; i < n; i++){
if(pq.empty()){
pq.push(nums[i] + i);
continue;
}
score = max(score, pq.top() + nums[i] - i);
pq.push(nums[i] + i);
}
return score;
}
};
First view😅
bhaiya, DP ke questions me sirf memoized solution tak aata hoga toh chalega kya OA aur interviews me?
Able to code on myself @10:04
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int ans = 0, maxi = values[0];
for(int j = 1; j < values.size(); j++) {
ans = max(ans, values[j] + maxi - j);
maxi = max(maxi, values[j] + j);
}
return ans;
}
};
I know, it took me a time to get to the approach to such a easy question.
solved with priority_queue
priority_queue pq;
int n=values.size();
pq.push(values[0]);
int res=0;
for(int j=1;j
i dont think jarurat thi
ek variable lke ho jata
@@HeetVichhivora video me variable lekar bataya hai MIK ne.
It was just a practice homework I think. to get familiar with heap.
@@gui-codes video dekhi nai sorry
@@gui-codes laga nai kuch dekne jesa isme
priority queue:
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int maxscore = INT_MIN;
int n = values.size()-1;
priority_queue pq;
pq.push(values[0]);
for(int i = 1;i
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int ans = 0;
priority_queue pq;
pq.push(values[0]);
for(int i = 1; i < values.size(); i++){
ans = max(ans,(int)pq.top() + values[i] - i);
pq.push(values[i] + i);
}
return ans;
}
};❤❤
sir min heap solution :-
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
priority_queuepq;
int result = INT_MIN;
for(int j=1;j
//priority queue approach
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int n=values.size();
priority_queue pq;
int res=0;
pq.push(values[0]);
for(int i=1;i
Using PQ,
class Solution {
public int maxScoreSightseeingPair(int[] values) {
int result = 0;
int n = values.length;
PriorityQueue pq = new PriorityQueue((a, b) -> (b-a));
for(int j=1;j
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
priority_queue pq;
pq.push(values[0]+0);
int res = INT_MIN;
for(int i =1;i
Done using priority_queue also :👇🙌
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
int maxi = INT_MIN;
priority_queuepq;
pq.push(values[0]);
for (int j = 1; j < n; j++) {
maxi = max(maxi, (pq.top() + values[j] - j));
pq.push(values[j]+j);
}
return maxi;
}
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
priority_queuepq;
pq.push(values[0]);
int ans = INT_MIN;
for(int i = 1; i < values.size(); i++){
int value = pq.top() + values[i] - i;
ans = max(ans, value);
pq.push(values[i] + i);
}
return ans;
}
};
Homework Done !!
ye dp se ho skta hai?
Single Traversal O(N) Time & O(1) Space Solution
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
int ans = -1e9;
int maxi = values[n-1] - n + 1;
for(int i=n-2;i>=0;i--){
ans=max(ans,values[i]+i+maxi);
maxi=max(maxi,values[i]-i);
}
return ans;
}
};
Bhaiya live stream kro
bhiyaa ambitious to hu apne dream k liye but lazyness or procastination hojati cheeje
best sir
Can you please make a video for Leetcode 3026. Maximum Good Subarray Sum?
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
int ans = INT_MIN;
priority_queue pq;
pq.push(values[0]);
for (int i = 1; i < n; i++) {
ans = max(ans, pq.top() + values[i] - i);
pq.push(values[i] + i);
}
return ans;
}
};
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
priority_queue pq;
pq.push(values[0]);
int result = 0;
for(int j = 1; j < n; j++)
{
int x = values[j] - j;
int y = pq.top();
result = max(result, x + y);
pq.push(values[j] + j);
}
return result;
}
};
Sir can u suggest how to start dp
Always study the concepts first.
Then move to Qns.
DP Concepts playlist - ruclips.net/p/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt&si=j4OPlfm8SFzxvsW2
Hope this helps ❤️🙏
class Solution {
public:
int maxScoreSightseeingPair(vector& val) {
int score = INT_MIN;
int maxleft = val[0]; // val[0]+0
for(int i=1 ; i
////////////////////////via pq
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
priority_queuepq;
int result = INT_MIN;
pq.push(values[0]+0);
for(int j = 1 ; j < values.size(); j++) {
int x = pq.top();
int y = values[j] - j;
result = max(result, x+y);
pq.push(values[j]+j);
}
return result;
}
};
Using Priority Queue:
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int n=values.size();
int ans=INT_MIN;
priority_queuepq;
for(int j=1;j
class Solution {
public int maxScoreSightseeingPair(int[] values) {
int n=values.length;
for(int i=0;i=0;i--){
temp[i]=Math.max(values[i+1],temp[i+1]);
}
for(int i=0;i
Best Solution :-> O(1) Space complexity and O(n) time complexity
class Solution {
public int maxScoreSightseeingPair(int[] values) {
int n=values.length;
int ans=-(int)(1e6);
int max=values[0];
for(int i=1;i
class Solution {
public int maxScoreSightseeingPair(int[] values) {
PriorityQueue pq = new PriorityQueue(Collections.reverseOrder());
int max =0;
for(int i=1;i
Using Priority Queue C++:
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
int ans = INT_MIN;
priority_queuepq;
pq.push(values[0]);
int i = 0;
for(int j=1;j
class Solution {
public int maxScoreSightseeingPair(int[] values) {
int n = values.length;
PriorityQueue pq = new PriorityQueue((a, b) -> b[0] - a[0]);
for(int i=0;i0;j--) {
while(pq.peek()[1] >= j) pq.poll();
max = Math.max(max, pq.peek()[0] + values[j] - j);
}
return max;
}
}
// rearranging equation to {(values[i] + i) + (values[j] - j)} where: i < j
// removing elmts from pq based on value takes log(n) time, while removing top elmt takes O(1) time
PriorityQueue using java
class Solution {
public int maxScoreSightseeingPair(int[] values) {
int n = values.length;
int max = 0;
int maxLeft = 0;
PriorityQueue maxheap = new PriorityQueue(Collections.reverseOrder());
maxheap.add(values[0]);
for(int i=1;i values[i] + i + values[j] - j;. we need to maximize the values[i] + i
class Solution {
public:
int maxScoreSightseeingPair(vector& values)
{
if(values.size()
Max Heap Solution:
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int ans = 0;
priority_queue pq;
pq.push(values[0] + 0);
for(int j = 1; j < values.size(); j++){
int x = pq.top() + (values[j] - j);
ans = max(ans, x);
pq.push(values[j] + j);
}
return ans;
}
};
/* Using Priority Queue ---> Homework done */
class Solution {
public int maxScoreSightseeingPair(int[] a) {
int n = a.length;
int res = -(int)1e9;
PriorityQueue q = new PriorityQueue(Comparator.reverseOrder());
q.add(a[0]);
for(int j = 1; j < n; j++){
res = Math.max(res, (a[j] - j + q.peek()));
int val = a[j] + j;
q.add(val);
}
return res;
}
}
PriorityQueue Solution in Java
class Solution {
public int maxScoreSightseeingPair(int[] values) {
PriorityQueue pq = new PriorityQueue((a, b) -> Integer.compare(b, a));
int max = 0;
pq.add(values[0]);
for(int i=1;i< values.length;i++){
max = Math.max(max,values[i]-i+ pq.peek());
pq.add(values[i]+i);
}
System.out.println(pq);
return max;
}
}
sir i solved it using DP
class Solution {
public:
int helper(int i, int count, vector &nums, vector &dp){
if(count == 0) return 0;
if(i == nums.size()){
if(count != 0) return -1e9;
else return 0;
}
int take;
int not_take;
if(dp[i][count] != -1) return dp[i][count];
if(count == 2){
take = nums[i] + i + helper(i + 1, count - 1, nums, dp);
not_take = helper(i + 1, count , nums, dp);
}
else if(count == 1){
take = nums[i] - i + helper(i + 1, count - 1, nums, dp);
not_take = helper(i + 1, count , nums, dp);
}
return dp[i][count] = max(take, not_take);
}
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
vector dp(n + 1, vector(3, - 1));
return helper(0, 2, values, dp);
}
};
Bro can you please help why did you choose to return a very small value when the count!=0 and not return 0
@@xyzb717
the logic behind that line was if you reach the end of the array and you still need to select some element (ie, count != 0) then this case is invalid and inorder to ignore this case i return a very small value (-1e9) so that this case does not effect my final answer
as in the last line we choose the maximum value from both the cases
ie, return dp[i][count] = max(take, not_take);
so by returning a very small value i ensure that the invalid case is never chosen
this question also solve by kadane algo aap ka algo me ek vector extra hain joki usko bhi reduce kar sakte hain direct ek extra variable le kar jo previous ka max rakhe ga but aap ke liye 🥰
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int sum =0;
int pre =values[0];
for(int j=1;j
bhai pura dekh le, bhaiya ne karaya hai is method se phi
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
priority_queuepq;
pq.push(values[0]+0);
int ans = INT_MIN;
for(int j=1;j
int maxScoreSightseeingPair(vector& values) {
int n=values.size();
// int maxval=values[0];
// int j=1;
int ans=INT_MIN;
// while(j
public int maxScoreSightseeingPair(int[]values){
int ans=0,i=0;
for(int j=1;j
def f(ar,i,k,m):
if i>=len(ar):
if k==0:
return 0
else :
return 0
if (i,k) in m:
return m[(i,k)]
np=0
p=0
np=0+f(ar,i+1,k,m)
for j in range (i+1,len(ar)):
p=max(p,ar[i]+i+ar[j]-j)
f(ar,i+1,k-1,m)
m[(i,k)]=max(p,np)
return m[(i,k)]
See i have this by Dinamic programming not that much optimize but works
Bobal
Done using priority queue class Solution {
public:
// using pq
int maxScoreSightseeingPair(vector& values) {
int n=values.size();
priority_queuepq;
pq.push(0+values[0]);
int ans=INT_MIN;
for(int i=1;i
took the equation hint then self solved:
int maxScoreSightseeingPair(vector& values) {
int sz = values.size(), ans=0;
vector a(values.begin(), values.end());
transform(a.begin(), a.end(), a.begin(), [i=0](int n) mutable { return n + i++;});
for(int i=1; i
RIP for those who were trying to solve using recursive approach 🥲
Nah actually it can be solved using recursion
@@nehasharmashorts8967 yup it can be, although i tried but got TLE , will be helpful if you show your recursive approach.
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int n = values.size();
priority_queuepq;
pq.push(values[0]);
int res = 0;
for(int j=1;j
class Solution {
public:
int maxScoreSightseeingPair(vector& values) {
int n=values.size();
priority_queuepq;
pq.push(values[0]+0);
int score=0;
for(int j=1;j