Maximum Ascending Subarray Sum - Leetcode 1800 - Python

NeetCodeIO · Intermediate ·⚡ Algorithms & Data Structures ·1y ago

Key Takeaways

The video solves LeetCode problem 1800, Maximum Ascending Subarray Sum, using a Brute Force solution and then optimizes it using a sliding window algorithm, ultimately achieving a linear time complexity and constant space complexity solution in Python.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem maximum ascending subay sum surprisingly an easy problem today but I'm recording this in advance so I don't know when this is actually going to be the daily problem but in this problem we are given an input array so let's consider the first example let's say this is the input array what we want to do is find the subarray which is basically just a contiguous part of the original array maybe the entire thing maybe just a single El element maybe this part and we want to identify the subarray such that we maximize the entire subarray sum so if you look at this subarray for example the entire sum is going to be 60 10 + 20 + 30 or maybe you could look at this subarray over here which is going to be 5 + 10 + 50 that's going to be 65 so this is bigger than this one and if you look at the output for this example 65 is the result that is actually the subarray that we want to identify and the reason for that is the reason we can't just take the entire subarray is because we want to ensure that for the subay that we choose in this case this one that the elements are in strictly increasing order they use the word ascending order so five is less than the next element which is 10 Which is less than the next element which is 50 if we try to add the 30 we see that that no longer holds we cannot include the 30 I mean I guess we could include the 30 if we wanted to but in that case we couldn't include the next element and if we can't include the next element then we kind of broke the contiguous part of this so even though like you could get rid of these two elements and say well 50 is bigger than 30 well now it's not contiguous anymore so you get rid of all of these and then you find okay well maybe the previous elements before 30 well yes 20 is less than 30 and then 10 is less than 20 so this is a valid subay but the sum is 60 it's not maximal we found the maximum subarray sum with the other subarray so how do you approach this problem well I think obviously there is a Brute Force solution and The Brute Force solution actually can lead you to the optimal solution The Brute Force would look something like this where we would have a couple nested for loops and the overall time complexity would end up being n squ it would look roughly like this where we start here we're at 10 so we could say this is our current subay sum and then we just want to expand as far right as we possibly can given this starting point so we see okay 10 that's bigger 30 that's bigger than the previous one five okay that's not quite bigger so we have to stop here this is the biggest one we could create starting from here now we could do something very very naive we could with the root Force solution say okay that's the best I could do starting from here but what's the best I could do starting from the second element and that would be 20 and 30 so I I want to show you the repeated work so this was the first iteration and then next I'm going to do this 20 and 30 and I can't go any further and then once again I'm going to try to find the biggest one starting from the third element and not to my surprise we still can't go any further this one was 30 okay now we do the same thing starting from the next element five and then 10 and then 50 and then we really can't go any further because there aren't any more elements we could do the same thing starting from this element 1050 and then finally we get uh the last element itself which is just 50 I think this picture is in some ways enough to identify the repeated work specifically it is this if I start at an element and I can find elements that are in increasing order well I'm going to do so I'm going to keep expanding as far as I can and then this is my stopping point I cannot go any further than that in addition we are guaranteed this is very important that every number in the input is going to be positive so it's not like this was a -10 if this was a -10 that would have actually been a problem because then yeah maybe this subarray over here could have actually been bigger than this one but given that all values are going to be positive that's not possible how could the next subet which is definitely going to end at the exact same position going to ever have a bigger sum than the the one we already calculated well it's not going to so what exactly is the solution in this well I wouldn't say it's precisely the sliding window uh algorithm but it does feel like a sliding window algorithm because what we're kind of doing is saying this is our starting point expand far to the right as you possibly can and then you found the stopping point okay can't go any further so next for the starting point we should shift it from here all the way to the next element because we can skip all of these subarrays we already know all of them are going to have a smaller sum than the one we just calculated we can skip those and so the way we're going to implement this is not by actually having two pointers that's why I'm saying it's not quite the sliding window algorithm what we're really going to do is this we're going to have a variable like the current sum which is going to tell us what the current sum is so first it'll be 10 then 10 + 20 then 10 + 20 + 30 so it'll be 60 and every step will also maintain what the result is which is going to be the maximum current sum that we've ever seen now this is what we're going to do once we get to the stopping point we're here we go to the next element we want to reset the current sum back down to zero and then add the next element so then set it to be five It's a Brand New Start it's a fresh start for us here and then we kind of do the same thing we just expand next element plus 10 next element is indeed bigger than this one so + 50 remember how did we identify this stopping point because the elements that are adjacent were not in increasing order 5 is not greater than 30 one tiny little Edge case that I think is probably worth mentioning is how we're going to go about implementing this because at every step we are going to look at two adjacent elements so if my pointer is over here my eye pointer then I want to look at the previous element and just make sure this value is greater than the previous one so the way I'm actually going to implement this algorithm is like this I'm going to have my current sum initially I'm actually going to set it to the first value which is going to be 10 and I'm also just going to set my result to that as well I don't really need to initialize it to zero I could that' probably be fine but setting it to the first value is also fine and then I'm actually not going to start my ey pointer at the first element I'm actually going to start it at the next element so now I can compare this with the previous one and it's greater so what I'm going to do is add a 20 to current so now it'll be 30 I'm going to update my result it's also 30 now I'm going to move my ey pointer here again compar with the previous it's bigger so I add 30 now my current is going to be 60 I can update the result as well next my ey pointer is going to be over here I look at the previous element it's not bigger so now is when I reset now I can reset my current value back down to this so it's going to be five now I could try to update my result but 60 is still the maximum that we've seen and next it's going to be a pretty quick so uh I'll get to 10 10 is bigger now my current will be 15 still we don't update the result once again my ey pointer is going to be shifted I'm at 50 now the value is bigger than the previous so we add 50 our current will be 65 and now we can update our result so this will be 65 and now we can't really go any further so this is what we would return so the nice thing about this solution is as you can see it just scans through the input once we uh reduce the time complexity from n^2 to linear and we don't need any extra data structures so the space complexity is constant now let's code it up so like I said I'm going to have two variables current is initially going to be the first element I think we're guaranteed that the array is going to be non-empty so we can actually get away with doing this and result is going to be the same I could just set it to Cur or the first element doesn't really matter that's what we're going to end up returning but not before we actually maximize it so we're going to go like this I in range length of nums but that's not our starting point we actually want to start at one and then go up until the end of the array so just like that the most important thing to do is the comparison we want to compare a nums of I with nums of I minus one we want to make sure that this is the case that the current element is bigger than the previous one so the way I could code this up is something like this I could say if else if it's true then we just add to current the element that we're looking at right now if it's not true then we could res Set current to the current element that we're looking at not including any of the previous values that we've seen and then after we've done that I think we could uh update our result like this try to maximize it and set it to the max of Cur and itself this will work let's give it a run you can see it's pretty efficient can't really do much better than this but if you prefer to write it without the if else it's actually possible you could do this you could change this to the not so kind of the ation I could have made this like greater than or equal as well but I'm just going to write it this way cuz I think this is also fine and so if that was not the case what we'd want to do is reset current just like we did in the else case but we could also actually be a little clever and set it to zero because if we do that then we can say we don't need an else statement and we could always take the current number and add it to Cur like this now this is really not an improvement over the previous solution in some ways I think this is less readable but I think it's worth showing you cuz usually in the medium and hard problems I always write code like this so I think it's kind of worth knowing some of these like little clever tricks so let me run this now and you can see here it also works if you found this helpful check out n code. thanks for watching and I'll see you soon

Original Description

🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews 🧑‍💼 LinkedIn: https://www.linkedin.com/in/navdeep-singh-3aaa14161/ 🐦 Twitter: https://twitter.com/neetcode1 ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf Problem Link: https://leetcode.com/problems/maximum-ascending-subarray-sum/ 0:00 - Read the problem 0:30 - Drawing Explanation 8:05 - Coding Explanation leetcode 1800 #neetcode #leetcode #python
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from NeetCodeIO · NeetCodeIO · 0 of 60

← Previous Next →
1 Leetcode 149 - Maximum Points on a Line - Python
Leetcode 149 - Maximum Points on a Line - Python
NeetCodeIO
 2 Design Linked List - Leetcode 707 - Python
Design Linked List - Leetcode 707 - Python
NeetCodeIO
 3 Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
NeetCodeIO
 4 Design Browser History - Leetcode 1472 - Python
Design Browser History - Leetcode 1472 - Python
NeetCodeIO
 5 Number of Good Paths - Leetcode 2421 - Python
Number of Good Paths - Leetcode 2421 - Python
NeetCodeIO
 6 Flip String to Monotone Increasing - Leetcode 926 - Python
Flip String to Monotone Increasing - Leetcode 926 - Python
NeetCodeIO
 7 Maximum Sum Circular Subarray - Leetcode 918 - Python
Maximum Sum Circular Subarray - Leetcode 918 - Python
NeetCodeIO
 8 Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
NeetCodeIO
 9 Concatenated Words - Leetcode 472 - Python
Concatenated Words - Leetcode 472 - Python
NeetCodeIO
 10 Data Stream as Disjoint Intervals - Leetcode 352 - Python
Data Stream as Disjoint Intervals - Leetcode 352 - Python
NeetCodeIO
 11 LFU Cache - Leetcode 460 - Python
LFU Cache - Leetcode 460 - Python
NeetCodeIO
 12 N-th Tribonacci Number - Leetcode 1137
N-th Tribonacci Number - Leetcode 1137
NeetCodeIO
 13 Best Team with no Conflicts - Leetcode 1626 - Python
Best Team with no Conflicts - Leetcode 1626 - Python
NeetCodeIO
 14 Greatest Common Divisor of Strings - Leetcode 1071 - Python
Greatest Common Divisor of Strings - Leetcode 1071 - Python
NeetCodeIO
 15 Shortest Path in a Binary Matrix - Leetcode 1091 - Python
Shortest Path in a Binary Matrix - Leetcode 1091 - Python
NeetCodeIO
 16 Insert into a Binary Search Tree - Leetcode 701 - Python
Insert into a Binary Search Tree - Leetcode 701 - Python
NeetCodeIO
 17 Delete Node in a BST - Leetcode 450 - Python
Delete Node in a BST - Leetcode 450 - Python
NeetCodeIO
 18 Shuffle the Array (Constant Space) - Leetcode 1470 - Python
Shuffle the Array (Constant Space) - Leetcode 1470 - Python
NeetCodeIO
 19 Fruits into Basket - Leetcode 904 - Python
Fruits into Basket - Leetcode 904 - Python
NeetCodeIO
 20 Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
NeetCodeIO
 21 Naming a Company - Leetcode 2306 - Python
Naming a Company - Leetcode 2306 - Python
NeetCodeIO
 22 As Far from Land as Possible - Leetcode 1162 - Python
As Far from Land as Possible - Leetcode 1162 - Python
NeetCodeIO
 23 Shortest Path with Alternating Colors - Leetcode 1129 - Python
Shortest Path with Alternating Colors - Leetcode 1129 - Python
NeetCodeIO
 24 Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
NeetCodeIO
 25 Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
NeetCodeIO
 26 Contains Duplicate II - Leetcode 219 - Python
Contains Duplicate II - Leetcode 219 - Python
NeetCodeIO
 27 Path with Maximum Probability - Leetcode 1514 - Python
Path with Maximum Probability - Leetcode 1514 - Python
NeetCodeIO
 28 Add to Array-Form of Integer - Leetcode 989 - Python
Add to Array-Form of Integer - Leetcode 989 - Python
NeetCodeIO
 29 Unique Paths II - Leetcode 63 - Python
Unique Paths II - Leetcode 63 - Python
NeetCodeIO
 30 Minimum Distance between BST Nodes - Leetcode 783 - Python
Minimum Distance between BST Nodes - Leetcode 783 - Python
NeetCodeIO
 31 Design Hashmap - Leetcode 706 - Python
Design Hashmap - Leetcode 706 - Python
NeetCodeIO
 32 Range Sum Query Immutable - Leetcode 303 - Python
Range Sum Query Immutable - Leetcode 303 - Python
NeetCodeIO
 33 Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
NeetCodeIO
 34 Middle of the Linked List - Leetcode 876 - Python
Middle of the Linked List - Leetcode 876 - Python
NeetCodeIO
 35 Course Schedule IV - Leetcode 1462 - Python
Course Schedule IV - Leetcode 1462 - Python
NeetCodeIO
 36 Single Element in a Sorted Array - Leetcode 540 - Python
Single Element in a Sorted Array - Leetcode 540 - Python
NeetCodeIO
 37 Capacity to Ship Packages - Leetcode 1011 - Python
Capacity to Ship Packages - Leetcode 1011 - Python
NeetCodeIO
 38 IPO - Leetcode 502 - Python
IPO - Leetcode 502 - Python
NeetCodeIO
 39 Minimize Deviation in Array - Leetcode 1675 - Python
Minimize Deviation in Array - Leetcode 1675 - Python
NeetCodeIO
 40 Longest Turbulent Array - Leetcode 978 - Python
Longest Turbulent Array - Leetcode 978 - Python
NeetCodeIO
 41 Last Stone Weight II - Leetcode 1049 - Python
Last Stone Weight II - Leetcode 1049 - Python
NeetCodeIO
 42 Construct Quad Tree - Leetcode 427 - Python
Construct Quad Tree - Leetcode 427 - Python
NeetCodeIO
 43 Find Duplicate Subtrees - Leetcode 652 - Python
Find Duplicate Subtrees - Leetcode 652 - Python
NeetCodeIO
 44 Sort an Array - Leetcode 912 - Python
Sort an Array - Leetcode 912 - Python
NeetCodeIO
 45 Ones and Zeroes - Leetcode 474 - Python
Ones and Zeroes - Leetcode 474 - Python
NeetCodeIO
 46 Remove Duplicates from Sorted Array II - Leetcode 80 - Python
Remove Duplicates from Sorted Array II - Leetcode 80 - Python
NeetCodeIO
 47 Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
NeetCodeIO
 48 Concatenation of Array - Leetcode 1929 - Python
Concatenation of Array - Leetcode 1929 - Python
NeetCodeIO
 49 Symmetric Tree - Leetcode 101 - Python
Symmetric Tree - Leetcode 101 - Python
NeetCodeIO
 50 Check Completeness of a Binary Tree - Leetcode 958 - Python
Check Completeness of a Binary Tree - Leetcode 958 - Python
NeetCodeIO
 51 Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
NeetCodeIO
 52 Find Peak Element - Leetcode 162 - Python
Find Peak Element - Leetcode 162 - Python
NeetCodeIO
 53 Accounts Merge - Leetcode 721 - Python
Accounts Merge - Leetcode 721 - Python
NeetCodeIO
 54 Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
NeetCodeIO
 55 Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
NeetCodeIO
 56 Number of Zero-Filled Subarrays - Leetcode 2348 - Python
Number of Zero-Filled Subarrays - Leetcode 2348 - Python
NeetCodeIO
 57 Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
NeetCodeIO
 58 Sqrt(x) - Leetcode 69 - Python
Sqrt(x) - Leetcode 69 - Python
NeetCodeIO
 59 Successful Pairs of Spells and Potions - Leetcode 2300 - Python
Successful Pairs of Spells and Potions - Leetcode 2300 - Python
NeetCodeIO
 60 Optimal Partition of String - Leetcode 2405 - Python
Optimal Partition of String - Leetcode 2405 - Python
NeetCodeIO

This video teaches how to solve the Maximum Ascending Subarray Sum problem on LeetCode using a Brute Force solution and then optimizing it using a sliding window algorithm to achieve better time and space complexity. The solution is implemented in Python.

Key Takeaways
  1. Expand subarray as far right as possible starting from a given element
  2. Identify elements in strictly increasing order
  3. Reset current sum to zero when not in increasing order
  4. Add next element to current sum if in increasing order
  5. Update result with maximum current sum seen so far
  6. Initialize current and result variables with the first element of the array
  7. Compare each element with the previous one and update current and result accordingly
💡 Using a sliding window algorithm can significantly improve the time complexity of the solution from O(n^2) to linear, making it more efficient for large inputs.

Related AI Lessons

⚡
Bloom Filters, Explained Properly
Learn how Bloom filters work and their benefits, including tiny memory and blazing speed, in exchange for potential false positives.
Dev.to · Daksh Gargas
 ⚡
Prefix Sums: The Preprocessing Trick That Makes Range Queries Instant
Learn how prefix sums enable instant range queries in arrays, boosting performance in various applications
Medium · Programming
 ⚡
I Thought I Was Ready for the Interview — Then One Simple Math Question Destroyed Me
A simple math question can destroy a developer's interview, highlighting the importance of being prepared for unexpected questions
Medium · Programming
 ⚡
Week 2(Day 10): LeetCode Two Pointers(slow & fast): Remove Duplicates from Sorted Array (Brute…
Learn to remove duplicates from a sorted array using the two pointers technique, improving from brute force to optimized solutions
Medium · Python

Chapters (3)

Read the problem
0:30 Drawing Explanation
8:05 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →