3165. Maximum Sum of Subsequence With Non-adjacent Elements | Bonus Qs + Hint | Weekly Leetcode 399

Segment Tree Series - bit.ly/segment-trees
*************************************************
Contest Link - leetcode.com/contest/weekly-c...
Problem Link - leetcode.com/contest/weekly-c...
Solution - leetcode.com/problems/maximum...
*************************************************
Timestamps -
00:00 - Agenda
01:30 - Problem Description
03:40 - [Brute force solution] Intuition
06:35 - [Brute force solution] Maximum subsequence sum
09:55 - [Brute force solution] Time Complexity
11:25 - Thought process to optimise
17:30 - [Merging Tree Nodes] Calculating "MAX_VAL"
25:29 - [Merging Tree Nodes] Calculating "SKIP_LAST"
31:53 - [Merging Tree Nodes] Calculating "SKIP_FIRST"
35:10 - [Merging Tree Nodes] Deriving "SKIP_LAST" with other values
39:05 - [Merging Tree Nodes] What variable we exactly need?
42:05 - [Merging Tree Nodes] Calculating "MAX_VAL" from final 2D array
43:55 - [Merging Tree Nodes] Recap of the Algorithm
45:32 - [Merging Tree Nodes] Pseudo code
48:31 - Final Algorithm
50:26 - Time Complexity
52:40 - Code Walkthrough
59:40 - Hint for Biweekly problem
*************************************************
Interview Experiences Playlists -
Microsoft - • Microsoft Interview Qu...
Amazon - • Amazon Interview Quest...
D.E.Shaw - • D.E.Shaw Interview Que...
Linkedin - • Linkedin Interview Que...
Facebook - • Facebook (Meta) Interv...
*********************************************************************
Please show support and subscribe if you find the content useful.

[@manaskumarpanda8961]

Superb Explanation sir🔥

[@krishanusaha5212]

Block placement query is easier than Maximum sum of subsquence...

[@krishankant3720]

True

[@ayushjaiswal2020]

you waited? of course.

[@raghavendrac4710]

Thank you sir!

[@jayantsharma3968]

Awesome explanation! Thankyou Mohan!!

[@hwgshvhd]

great explanation!

[@karthikreddy8965]

in the definition of the node just replacing vector into an array ie int val [2][2] gives ac to your solution .. the problem was you are using too many resizes using the vector..also you could use ios_base::sync blah blah to further improve on it

[@codingmohan]

Thanks!Vector to array was a nice catch.
Also I don't think ios_base applies here as the input and output is performed before our function is call, did you ever try that in the past in leetcode?

[@karthikreddy8965]

@@codingmohan i didnt believe in it too.. but i could see some 50 ms improvement for 350 ms run time...

[@krishanusaha5212]

Awesome explanation, thake you bhaiya ❤

[@problematicpuzzlechannel6663]

When merging the node, why is it ans[i][j] = max(ans[i][j], lft[i][k] + rgt[1 - k][j]) ? Do we have to also consider this case: lft[i][0] + rgt[0][j], where last element of lft and first element of rgt is not selected

[@codingmohan]

You can consider that case as well but that should already be covered in rgt[1][j] because the definition of the values in this array is "what is the maximum value we can have if we start with this index". Therefore if there is a scenario where not choosing the 1st index would yield better results, the value will reflect the same.
Hope that clarifies.

[@nikhilprakash729]

Awesome Explanation

[@nabajyotimajumdar4511]

Awesome question, awesome explanation

[@prithwirajmitra3811]

Superb 🔥. Can you solve the Biweekly Contest 131 4th question ?

[@rajatmantri9141]

nice explanation

[@rajatmantri9141]

sir could you plz make video on block placement queries

[@raisanjeeb42]

I tried by creating segmentTree of vector of size 4 instead of Struct Node and it passed all test case . I meant Tree.resize(4*n,vector(4,0))
I must say thank tou for the efforts you put in to explain. beautiful explanation

[@raghavendrac4710]

Thank you sir!