title
Kadane's Algorithm | Maximum Subarray Sum | Finding and Printing

description
Problem Link: https://bit.ly/3QhMl6j Notes/C++/Java/Python codes: https://takeuforward.org/data-structure/kadanes-algorithm-maximum-subarray-sum-in-an-array/ We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition. Full Course: https://bit.ly/tufA2ZYt You can follow me across social media, all my handles are below: Linkedin/Instagram/Telegram: https://linktr.ee/takeUforward Time Stamp 0:00 - Introduction to course 0:41 - Problem Statement 2:13 - Brute Force Solution 6:12 - Better Solution 7:40 - Optimal (Kadane's Algorithm) 13:18 - Code 15:29 - Time Complexity 15:40 - Follow up question 19:37 - Outro

detail
{'title': "Kadane's Algorithm | Maximum Subarray Sum | Finding and Printing", 'heatmap': [{'end': 956.243, 'start': 857.607, 'weight': 0.977}, {'end': 1178.27, 'start': 1147.346, 'weight': 0.925}], 'summary': "The stribers a2z dsa course contains 455 modules and 400+ problems, aiming to ensure proficiency in ds algorithms globally. it covers concepts like maximum subarray sum, brute force approach with o(n^3) time complexity, subarray sum iteration, kadane's algorithm, and a modified algorithm for finding and printing the subarray with the maximum sum.", 'chapters': [{'end': 42.191, 'segs': [{'end': 42.191, 'src': 'embed', 'start': 3.1, 'weight': 0, 'content': [{'end': 4.28, 'text': 'Hey everyone, welcome back to the channel.', 'start': 3.1, 'duration': 1.18}, {'end': 5.821, 'text': 'I hope you guys are doing extremely well.', 'start': 4.3, 'duration': 1.521}, {'end': 9.421, 'text': 'So this is another video from the Stribers A2Z DSA course.', 'start': 6.201, 'duration': 3.22}, {'end': 14.062, 'text': "Just in case you're for the first time here, this is world's most in-depth course when it comes to DS Algo.", 'start': 9.801, 'duration': 4.261}, {'end': 17.363, 'text': 'Why do I say that? Because this course has 455 modules.', 'start': 14.442, 'duration': 2.921}, {'end': 22.064, 'text': 'By the end of the course, you would have solved more than 400 plus problems in DS Algo.', 'start': 17.683, 'duration': 4.381}, {'end': 23.884, 'text': 'And you can go across the entire internet.', 'start': 22.344, 'duration': 1.54}, {'end': 25.264, 'text': 'You can buy any of the paid courses.', 'start': 23.904, 'duration': 1.36}, {'end': 28.265, 'text': 'None of them will be teaching you DS Algo in such depth.', 'start': 25.744, 'duration': 2.521}, {'end': 32.907, 'text': 'Something that I can give you as guarantee is if you complete this entire course,', 'start': 29.105, 'duration': 3.802}, {'end': 36.809, 'text': 'you can clear any of the DS algorithms in any of the companies in any part of the world.', 'start': 32.907, 'duration': 3.902}, {'end': 42.191, 'text': 'So till now we have covered till majority element in step 3.2.', 'start': 37.229, 'duration': 4.962}], 'summary': 'Stribers a2z dsa course offers 455 modules and 400+ problems, guaranteeing expertise in ds algo.', 'duration': 39.091, 'max_score': 3.1, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k43100.jpg'}], 'start': 3.1, 'title': 'Stribers a2z dsa overview', 'summary': 'An overview of the stribers a2z dsa course, containing 455 modules and covering 400+ problems in ds algo, ensuring proficiency in clearing ds algorithms globally.', 'chapters': [{'end': 42.191, 'start': 3.1, 'title': 'Stribers a2z dsa course overview', 'summary': 'An overview of the stribers a2z dsa course, which consists of 455 modules and covers over 400+ problems in ds algo, guaranteeing proficiency in clearing ds algorithms in any company worldwide.', 'duration': 39.091, 'highlights': ['The Stribers A2Z DSA course comprises 455 modules, and students would have solved more than 400+ problems in DS Algo by the end of the course.', 'Completing the entire course guarantees proficiency in clearing DS algorithms in any company worldwide.', "The course provides the world's most in-depth training in DS Algo, surpassing any paid courses available online."]}], 'duration': 39.091, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k43100.jpg', 'highlights': ['The Stribers A2Z DSA course comprises 455 modules, and students would have solved more than 400+ problems in DS Algo by the end of the course.', "The course provides the world's most in-depth training in DS Algo, surpassing any paid courses available online.", 'Completing the entire course guarantees proficiency in clearing DS algorithms in any company worldwide.']}, {'end': 384.16, 'segs': [{'end': 68.919, 'src': 'embed', 'start': 42.191, 'weight': 2, 'content': [{'end': 47.714, 'text': "In this video, we will be covering maximum subarray sum, which will be involving Pradhan's algorithm.", 'start': 42.191, 'duration': 5.523}, {'end': 50.315, 'text': 'So what does the problem see? Subarray.', 'start': 47.894, 'duration': 2.421}, {'end': 52.144, 'text': 'out of all the subarrays.', 'start': 51.243, 'duration': 0.901}, {'end': 55.187, 'text': 'Give me the maximum sum.', 'start': 52.865, 'duration': 2.322}, {'end': 60.792, 'text': 'Now, what is the definition of subarray? The definition of subarray is a contagious part of the array.', 'start': 55.587, 'duration': 5.205}, {'end': 63.614, 'text': "I've already explained you this in the previous videos.", 'start': 61.032, 'duration': 2.582}, {'end': 68.919, 'text': 'Now, what is a contagious part? Something like this, minus 1, minus 2.', 'start': 64.055, 'duration': 4.864}], 'summary': "Covering maximum subarray sum with pradhan's algorithm.", 'duration': 26.728, 'max_score': 42.191, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k442191.jpg'}, {'end': 170.854, 'src': 'embed', 'start': 129.098, 'weight': 0, 'content': [{'end': 132.703, 'text': 'And that is what you have to return as the answer to this problem.', 'start': 129.098, 'duration': 3.605}, {'end': 134.806, 'text': 'Now this question comes up in an interview.', 'start': 133.084, 'duration': 1.722}, {'end': 138.691, 'text': "What is the first approach that you'll be giving to the interviewer? That's definitely.", 'start': 134.866, 'duration': 3.825}, {'end': 144.516, 'text': "trying out all sub arrays and we've already discussed how do we do that in the previous video.", 'start': 139.372, 'duration': 5.144}, {'end': 148.879, 'text': 'just in case you do not know, please go back and watch the previous videos in this playlist.', 'start': 144.516, 'duration': 4.363}, {'end': 149.88, 'text': "you'll understand.", 'start': 148.879, 'duration': 1.001}, {'end': 154.163, 'text': 'how do you print all the sub arrays or how do you iterate through all the sub arrays?', 'start': 149.88, 'duration': 4.283}, {'end': 161.028, 'text': 'so if you try out all the sub arrays and out of all the sub arrays, which gives you the maximum sum, can actually be uh,', 'start': 154.163, 'duration': 6.865}, {'end': 163.81, 'text': 'the answer will actually be the answer.', 'start': 161.889, 'duration': 1.921}, {'end': 165.671, 'text': 'So how do you try out all the sub-arrays?', 'start': 164.11, 'duration': 1.561}, {'end': 170.854, 'text': 'If I have a clear observation, we know this is the first sub-array.', 'start': 166.072, 'duration': 4.782}], 'summary': 'In an interview question, the first approach is to try out all subarrays to find the one with the maximum sum.', 'duration': 41.756, 'max_score': 129.098, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k4129098.jpg'}, {'end': 389.965, 'src': 'embed', 'start': 362.241, 'weight': 1, 'content': [{'end': 367.103, 'text': 'Am I using any space? No, the space complexity is being bigo of 1.', 'start': 362.241, 'duration': 4.862}, {'end': 372.107, 'text': 'So, what I can say is, This will be the extremist brute force solution.', 'start': 367.103, 'duration': 5.004}, {'end': 375.911, 'text': 'This is where the interviewer will come up and say can you please optimize the brute force?', 'start': 372.488, 'duration': 3.423}, {'end': 377.914, 'text': 'Then you move to the better solution.', 'start': 376.412, 'duration': 1.502}, {'end': 379.595, 'text': 'and the better solution is very, very easy.', 'start': 377.914, 'duration': 1.681}, {'end': 384.16, 'text': "What we do is we say, okay, let's for a moment, erase this up.", 'start': 380.016, 'duration': 4.144}, {'end': 385.762, 'text': 'For a moment, erase this out.', 'start': 384.781, 'duration': 0.981}, {'end': 387.263, 'text': "Let's do some observations.", 'start': 386.082, 'duration': 1.181}, {'end': 389.965, 'text': 'The first subarray was minus 2.', 'start': 388.103, 'duration': 1.862}], 'summary': 'The space complexity is o(1), transitioning from brute force to a better solution.', 'duration': 27.724, 'max_score': 362.241, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k4362241.jpg'}], 'start': 42.191, 'title': 'Maximum subarray sum and its brute force approach', 'summary': 'Explains the concept of maximum subarray sum and the brute force approach of iterating through all subarrays to find the maximum sum, with a time complexity of o(n^3) and a space complexity of o(1).', 'chapters': [{'end': 170.854, 'start': 42.191, 'title': 'Maximum subarray sum', 'summary': 'Explains the concept of maximum subarray sum, which involves finding the maximum sum within a contiguous part of an array and discusses the approach of trying out all subarrays to find the maximum sum.', 'duration': 128.663, 'highlights': ['The problem involves finding the maximum sum within a contiguous part of an array, where even a single element and the entire array can be considered as subarrays.', 'The definition of subarray is a contagious part of the array, and trying out all subarrays to find the maximum sum is an approach discussed.', 'The approach of trying out all subarrays to find the maximum sum is recommended as the first approach in an interview scenario.']}, {'end': 384.16, 'start': 170.854, 'title': 'Subarray sum brute force', 'summary': 'Explains the process of iterating through all the subarrays of an array to find the maximum sum, using a brute force solution with a time complexity of approximately o(n^3) and a space complexity of o(1).', 'duration': 213.306, 'highlights': ['The process involves iterating through all the subarrays of the given array to find the maximum sum, with each iteration involving three loops, resulting in a time complexity of approximately O(n^3).', 'The space complexity of the brute force solution is O(1), as it does not require any additional space for computation.', 'The initial brute force solution is considered an extremist approach, and the interviewer may prompt for optimization, leading to a better solution.', 'The better solution, as mentioned, is a straightforward optimization over the brute force approach.']}], 'duration': 341.969, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k442191.jpg', 'highlights': ['The process involves iterating through all the subarrays of the given array to find the maximum sum, with each iteration involving three loops, resulting in a time complexity of approximately O(n^3)', 'The space complexity of the brute force solution is O(1), as it does not require any additional space for computation', 'The problem involves finding the maximum sum within a contiguous part of an array, where even a single element and the entire array can be considered as subarrays', 'The approach of trying out all subarrays to find the maximum sum is recommended as the first approach in an interview scenario', 'The initial brute force solution is considered an extremist approach, and the interviewer may prompt for optimization, leading to a better solution']}, {'end': 764.697, 'segs': [{'end': 446.404, 'src': 'embed', 'start': 404.595, 'weight': 1, 'content': [{'end': 407.757, 'text': 'Whatever was the sum of the previous subarray, hear me out properly.', 'start': 404.595, 'duration': 3.162}, {'end': 411.9, 'text': 'whatever was the sum of the previous, i just add the next element.', 'start': 408.177, 'duration': 3.723}, {'end': 413.16, 'text': 'then i add the next element.', 'start': 411.9, 'duration': 1.26}, {'end': 415.242, 'text': 'so sum over here will become minus five.', 'start': 413.16, 'duration': 2.082}, {'end': 417.363, 'text': 'sum over here, including four, will become one.', 'start': 415.242, 'duration': 2.121}, {'end': 419.485, 'text': 'so you just add the next element.', 'start': 417.363, 'duration': 2.122}, {'end': 422.887, 'text': 'whenever j was initially here, take this, and j goes here.', 'start': 419.485, 'duration': 3.402}, {'end': 424.128, 'text': 'take this, and j goes here.', 'start': 422.887, 'duration': 1.241}, {'end': 425.049, 'text': 'takes this.', 'start': 424.128, 'duration': 0.921}, {'end': 429.191, 'text': "so eventually you'll get the summary three like three element sum stored.", 'start': 425.049, 'duration': 4.142}, {'end': 434.075, 'text': "so what i'll do is i'll take this sum out and i'll say some, can you stay here?", 'start': 429.191, 'duration': 4.884}, {'end': 438.862, 'text': 'and some as you move forward, Can you just add up array of j?', 'start': 434.075, 'duration': 4.787}, {'end': 440.362, 'text': 'So first time this gets added.', 'start': 439.122, 'duration': 1.24}, {'end': 441.783, 'text': 'So we have one subarray sum.', 'start': 440.642, 'duration': 1.141}, {'end': 443.143, 'text': 'Next time this gets added.', 'start': 442.043, 'duration': 1.1}, {'end': 444.124, 'text': 'So we have two subarray sum.', 'start': 443.163, 'duration': 0.961}, {'end': 445.464, 'text': 'Next time this gets added.', 'start': 444.444, 'duration': 1.02}, {'end': 446.404, 'text': 'So we have three subarray sum.', 'start': 445.484, 'duration': 0.92}], 'summary': 'Summarizing array subarray sums, 3 subarray sums achieved.', 'duration': 41.809, 'max_score': 404.595, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k4404595.jpg'}, {'end': 498.026, 'src': 'embed', 'start': 469.673, 'weight': 0, 'content': [{'end': 474.134, 'text': "So in order to find the most optimal solution, we will be using something known as the Cadan's algorithm.", 'start': 469.673, 'duration': 4.461}, {'end': 479.076, 'text': "Again, I'll be explaining the algo as well as the intuition behind the algorithm.", 'start': 474.514, 'duration': 4.562}, {'end': 480.276, 'text': 'Do not worry about that.', 'start': 479.416, 'duration': 0.86}, {'end': 485.117, 'text': "The first thing that you'll do is you will say maximum to be the lowest number.", 'start': 480.596, 'duration': 4.521}, {'end': 491.519, 'text': 'And assume you say int mean, and then you start from the zeroth index.', 'start': 486.858, 'duration': 4.661}, {'end': 498.026, 'text': 'and you take a sum initially as zero, and I even start iterating in the array.', 'start': 492.563, 'duration': 5.463}], 'summary': "Using cadan's algorithm to find the most optimal solution, starting with maximum as the lowest number and iterating through the array.", 'duration': 28.353, 'max_score': 469.673, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k4469673.jpg'}, {'end': 590.988, 'src': 'embed', 'start': 560.915, 'weight': 5, 'content': [{'end': 565.276, 'text': 'And if you took two elements, the sum was minus 5.', 'start': 560.915, 'duration': 4.361}, {'end': 568.057, 'text': 'By the way, minus 3 is greater than minus 5.', 'start': 565.276, 'duration': 2.781}, {'end': 569.238, 'text': 'A lot of people get confused.', 'start': 568.057, 'duration': 1.181}, {'end': 571.538, 'text': 'Minus 3 is greater than minus 5.', 'start': 569.478, 'duration': 2.06}, {'end': 573.719, 'text': 'So will it make sense to carry a minus?', 'start': 571.538, 'duration': 2.181}, {'end': 581.542, 'text': 'Because if you carry negative sum, if you carry negative sum forward, the summation will always reduce, will always reduce.', 'start': 574.139, 'duration': 7.403}, {'end': 583.303, 'text': 'It is minus 3.', 'start': 582.222, 'duration': 1.081}, {'end': 585.264, 'text': 'Since you carried a negative, it will always reduce.', 'start': 583.303, 'duration': 1.961}, {'end': 590.988, 'text': 'So what you will do is, at any moment, the sum is lesser than 0.', 'start': 585.584, 'duration': 5.404}], 'summary': 'The sum of two elements was -5, and carrying negative sum will always reduce the summation to less than 0.', 'duration': 30.073, 'max_score': 560.915, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k4560915.jpg'}], 'start': 384.781, 'title': "Subarray sum iteration and kadane's algorithm", 'summary': "Discusses iterating through subarrays to calculate three subarray sums and explains kadane's algorithm for finding the optimal solution by maximizing subarray sums and neglecting negative sums.", 'chapters': [{'end': 446.404, 'start': 384.781, 'title': 'Subarray sum iteration', 'summary': 'Discusses the process of iterating through subarrays and updating the sum by adding the next element, resulting in the gradual calculation of subarray sums and a total of three subarray sums.', 'duration': 61.623, 'highlights': ['The process involves iteratively updating the sum of subarrays by adding the next element, resulting in the gradual calculation of subarray sums, with a total of three subarray sums.', 'The sum of the previous subarray is used as a starting point, and the next element is added to it, leading to the calculation of subarray sums like minus five and one.', 'The technique of adding the next element to the sum of the previous subarray results in the calculation of subarray sums, leading to the generation of one, two, and three subarray sums.']}, {'end': 764.697, 'start': 446.765, 'title': "Finding optimal solution with kadane's algorithm", 'summary': "Explains the kadane's algorithm for finding the most optimal solution in an array, showcasing the thought process and decision-making for selecting subarrays to maximize the sum, and emphasizing the importance of neglecting negative sums to enhance the overall result.", 'duration': 317.932, 'highlights': ["The chapter introduces the Kadane's algorithm for finding the most optimal solution in an array, emphasizing the thought process and decision-making for selecting subarrays to maximize the sum. It explains the importance of neglecting negative sums to enhance the overall result.", 'The algorithm involves starting with a maximum set to the lowest number, iterating through the array, and updating the maximum when a better sum is encountered, showcasing a step-by-step thought process for selecting subarrays to maximize the sum.', 'The explanation emphasizes the importance of neglecting negative sums to enhance the overall result, as carrying negative sums forward will always reduce the summation, and only positive sums contribute to increasing the overall sum.']}], 'duration': 379.916, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k4384781.jpg', 'highlights': ["The chapter introduces Kadane's algorithm for finding the most optimal solution in an array, emphasizing the thought process and decision-making for selecting subarrays to maximize the sum.", 'The process involves iteratively updating the sum of subarrays by adding the next element, resulting in the gradual calculation of subarray sums, with a total of three subarray sums.', 'The sum of the previous subarray is used as a starting point, and the next element is added to it, leading to the calculation of subarray sums like minus five and one.', 'The technique of adding the next element to the sum of the previous subarray results in the calculation of subarray sums, leading to the generation of one, two, and three subarray sums.', 'The algorithm involves starting with a maximum set to the lowest number, iterating through the array, and updating the maximum when a better sum is encountered, showcasing a step-by-step thought process for selecting subarrays to maximize the sum.', 'The explanation emphasizes the importance of neglecting negative sums to enhance the overall result, as carrying negative sums forward will always reduce the summation, and only positive sums contribute to increasing the overall sum.']}, {'end': 1199.376, 'segs': [{'end': 815.263, 'src': 'embed', 'start': 789.926, 'weight': 0, 'content': [{'end': 794.988, 'text': "That's how you will get the maximum subarray sum as 7.", 'start': 789.926, 'duration': 5.062}, {'end': 797.269, 'text': 'I will explain you how to find the subarray as well.', 'start': 794.988, 'duration': 2.281}, {'end': 803.411, 'text': "But as of now, let's code this one and then we will move to coding how to find that particular subarray.", 'start': 797.469, 'duration': 5.942}, {'end': 804.852, 'text': "Okay, so let's code this off.", 'start': 803.671, 'duration': 1.181}, {'end': 806.613, 'text': 'Again, the problem link will be in the description.', 'start': 804.952, 'duration': 1.661}, {'end': 809.514, 'text': 'Please make sure you try out the problem from the problem link itself.', 'start': 806.653, 'duration': 2.861}, {'end': 813.021, 'text': 'long long sum equal to zero.', 'start': 810.339, 'duration': 2.682}, {'end': 815.263, 'text': 'maxi equal to not.', 'start': 813.021, 'duration': 2.242}], 'summary': 'Explanation of finding the maximum subarray sum and coding it with problem link provided.', 'duration': 25.337, 'max_score': 789.926, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k4789926.jpg'}, {'end': 956.243, 'src': 'heatmap', 'start': 857.607, 'weight': 0.977, 'content': [{'end': 864.428, 'text': "But wait, in this particular problem, in this particular problem, they have said you're given an array.", 'start': 857.607, 'duration': 6.821}, {'end': 867.711, 'text': 'you have to find the sum of the subarray, including empty subarray.', 'start': 864.428, 'duration': 3.283}, {'end': 868.712, 'text': 'including empty subarray.', 'start': 867.711, 'duration': 1.001}, {'end': 871.033, 'text': 'Now, let me take you to one more example.', 'start': 869.052, 'duration': 1.981}, {'end': 875.036, 'text': 'Imagine it is minus 4, minus 2, minus 3, minus 1.', 'start': 871.614, 'duration': 3.422}, {'end': 881.101, 'text': 'In this case, which is the, like, according to our definition, I can say, this is the subarray.', 'start': 875.036, 'duration': 6.065}, {'end': 885.244, 'text': 'So, I can say, this minus 1 is the subarray, which gives me the maximum sum.', 'start': 881.321, 'duration': 3.923}, {'end': 888.167, 'text': 'Again, minus 4 is not greater than minus 1.', 'start': 885.344, 'duration': 2.823}, {'end': 894.491, 'text': 'So this subarray is a In this particular problem they have explicitly mentioned.', 'start': 888.167, 'duration': 6.324}, {'end': 900.876, 'text': "if you do not find any subarray with greater than zero sound, then you just say fine, I'll take an empty subarray.", 'start': 894.491, 'duration': 6.385}, {'end': 902.437, 'text': 'And this is what you call empty.', 'start': 901.396, 'duration': 1.041}, {'end': 903.838, 'text': 'I will not take anyone.', 'start': 902.997, 'duration': 0.841}, {'end': 904.819, 'text': 'I will not take anyone.', 'start': 904.018, 'duration': 0.801}, {'end': 906.5, 'text': 'If I do not take anyone, it will be zero.', 'start': 905.099, 'duration': 1.401}, {'end': 914.845, 'text': "So what you'll do at the end is before returning, if by chance maximum is lesser than zero, you will reinitialize that to zero.", 'start': 906.96, 'duration': 7.885}, {'end': 916.646, 'text': 'Because of this one.', 'start': 915.966, 'duration': 0.68}, {'end': 917.567, 'text': 'Because of this one.', 'start': 916.966, 'duration': 0.601}, {'end': 921.549, 'text': 'Where it states, if none of them is giving you a positive sum, return zero.', 'start': 917.907, 'duration': 3.642}, {'end': 922.99, 'text': "Because you'll take no one.", 'start': 921.629, 'duration': 1.361}, {'end': 926.893, 'text': "And then you'll go ahead and say, okay, now I can easily go ahead and submit this.", 'start': 923.371, 'duration': 3.522}, {'end': 928.254, 'text': "Let's see if it's running fine or not.", 'start': 927.193, 'duration': 1.061}, {'end': 931.015, 'text': 'guys, what is the time complexity?', 'start': 929.034, 'duration': 1.981}, {'end': 940.861, 'text': 'very simple the time complexity is b go of n, and the space complexity is b go of 1, because we are not using any extra space whatsoever.', 'start': 931.015, 'duration': 9.846}, {'end': 945.904, 'text': 'so, once you give the optimal solution to the interviewer, the interviewer now might ask you a follow-up question,', 'start': 940.861, 'duration': 5.043}, {'end': 954.821, 'text': 'and that will be can you print the subarray with a maximum sum, and he might ask you to print any of those subarrays.', 'start': 945.904, 'duration': 8.917}, {'end': 956.243, 'text': 'why do i say any of those?', 'start': 954.821, 'duration': 1.422}], 'summary': 'Given array, find subarray sum, including empty subarray. time complexity: o(n), space complexity: o(1).', 'duration': 98.636, 'max_score': 857.607, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k4857607.jpg'}, {'end': 986.464, 'src': 'embed', 'start': 956.243, 'weight': 2, 'content': [{'end': 957.986, 'text': 'there might be multiple subarrays.', 'start': 956.243, 'duration': 1.743}, {'end': 963.112, 'text': 'okay. so you might ask you to print any of those subarrays, which will give you a maximum sum.', 'start': 957.986, 'duration': 5.126}, {'end': 972.439, 'text': 'now for this follow-up question, you just have to slightly do some changes to the given code that we wrote, which was finding out the maximum sum.', 'start': 963.112, 'duration': 9.327}, {'end': 976.9, 'text': "Now, what are the changes? Let's quickly analyze the algorithm once again.", 'start': 972.699, 'duration': 4.201}, {'end': 978.681, 'text': 'So what did we do??', 'start': 977.401, 'duration': 1.28}, {'end': 986.464, 'text': 'We had a maxi, as int mean, and we started the sum as zero and we started from the first and we had a minus two added correct?', 'start': 979.201, 'duration': 7.263}], 'summary': 'Algorithm to find maximum sum in subarrays with slight modifications', 'duration': 30.221, 'max_score': 956.243, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k4956243.jpg'}, {'end': 1066.536, 'src': 'embed', 'start': 1035.234, 'weight': 1, 'content': [{'end': 1043.364, 'text': "So what I can say is, okay, if sum is zero, I can say I'm starting off.", 'start': 1035.234, 'duration': 8.13}, {'end': 1047.987, 'text': "I'm starting off a new subarray whose sum has to be computed.", 'start': 1044.085, 'duration': 3.902}, {'end': 1056.191, 'text': 'Now what I will add is, this time I will add an answer start and answer end.', 'start': 1048.467, 'duration': 7.724}, {'end': 1062.694, 'text': "This is what I'll add, like two new variables, initially initialized as minus one.", 'start': 1056.991, 'duration': 5.703}, {'end': 1066.536, 'text': "Now what I'll do is I'll say if summation is greater than maximum.", 'start': 1063.094, 'duration': 3.442}], 'summary': 'Algorithm to find maximum subarray sum.', 'duration': 31.302, 'max_score': 1035.234, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k41035233.jpg'}, {'end': 1178.27, 'src': 'heatmap', 'start': 1147.346, 'weight': 0.925, 'content': [{'end': 1155.735, 'text': "The time complexity still stays as b go of n and the space complexity is b go of 1 for Cadan's algorithm, even if you find the subarray sum,", 'start': 1147.346, 'duration': 8.389}, {'end': 1156.797, 'text': 'or even if you find the subarray.', 'start': 1155.735, 'duration': 1.062}, {'end': 1157.618, 'text': "I hope that's clear.", 'start': 1157.017, 'duration': 0.601}, {'end': 1160.379, 'text': 'So coming back to the sheet, I can say that this one is done and also this one.', 'start': 1157.978, 'duration': 2.401}, {'end': 1163.921, 'text': 'Why? Because we already have a video made on this and this video was made recently.', 'start': 1160.439, 'duration': 3.482}, {'end': 1167.243, 'text': 'It might have a DP tag, but it does not involve any dynamic programming.', 'start': 1164.122, 'duration': 3.121}, {'end': 1169.845, 'text': 'Why? Because this video was the base of the next set of problems.', 'start': 1167.263, 'duration': 2.582}, {'end': 1172.246, 'text': 'DP 36, 37, 38 is the base of this one.', 'start': 1169.885, 'duration': 2.361}, {'end': 1176.589, 'text': 'That is why you can just watch it without any prior knowledge of dynamic programming.', 'start': 1172.266, 'duration': 4.323}, {'end': 1178.27, 'text': 'So I hope you have understood everything.', 'start': 1176.809, 'duration': 1.461}], 'summary': 'Cadans algorithm has time complexity o(n) and space complexity o(1). dp 36, 37, 38 videos are base for the next set.', 'duration': 30.924, 'max_score': 1147.346, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k41147346.jpg'}, {'end': 1193.034, 'src': 'embed', 'start': 1164.122, 'weight': 4, 'content': [{'end': 1167.243, 'text': 'It might have a DP tag, but it does not involve any dynamic programming.', 'start': 1164.122, 'duration': 3.121}, {'end': 1169.845, 'text': 'Why? Because this video was the base of the next set of problems.', 'start': 1167.263, 'duration': 2.582}, {'end': 1172.246, 'text': 'DP 36, 37, 38 is the base of this one.', 'start': 1169.885, 'duration': 2.361}, {'end': 1176.589, 'text': 'That is why you can just watch it without any prior knowledge of dynamic programming.', 'start': 1172.266, 'duration': 4.323}, {'end': 1178.27, 'text': 'So I hope you have understood everything.', 'start': 1176.809, 'duration': 1.461}, {'end': 1183.311, 'text': "Just in case you have, please, please do consider giving that like to us because it won't cost you anything, but it does motivate me.", 'start': 1178.53, 'duration': 4.781}, {'end': 1188.053, 'text': "And to continue our tradition, please do comment understood so that I get an idea that you've understood everything that I'm teaching.", 'start': 1183.671, 'duration': 4.382}, {'end': 1193.034, 'text': "And yes, if you haven't followed me on social media, that is Instagram, Twitter, LinkedIn, all the links will be in the description.", 'start': 1188.473, 'duration': 4.561}], 'summary': 'Dp 36, 37, 38 forms the base of this video, enabling understanding without prior knowledge of dynamic programming.', 'duration': 28.912, 'max_score': 1164.122, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k41164122.jpg'}], 'start': 764.697, 'title': 'Finding maximum subarray sum', 'summary': 'Demonstrates how to find the maximum subarray sum, which is 7, using an algorithm with time complexity of o(n) and space complexity of o(1), and suggests a modification for printing the subarray with the maximum sum.', 'chapters': [{'end': 813.021, 'start': 764.697, 'title': 'Finding maximum subarray sum', 'summary': 'Demonstrates how to find the maximum subarray sum, which is 7, using a pronounced algorithm that involves adding and drawing when the sum goes below 0.', 'duration': 48.324, 'highlights': ['The pronounced algorithm states that by continuously adding and drawing when the sum goes below 0, the maximum subarray sum can be found as 7.', 'The result of finding the maximum subarray sum is 7.']}, {'end': 1199.376, 'start': 813.021, 'title': 'Maximum subarray sum', 'summary': 'Illustrates an algorithm to find the maximum subarray sum, with time complexity of o(n) and space complexity of o(1), and suggests a modification for printing the subarray with the maximum sum.', 'duration': 386.355, 'highlights': ['The algorithm computes the maximum subarray sum by iterating through the array and updating the sum, re-initializing it to 0 if it becomes negative, and updating the maximum if the current sum exceeds it.', 'The modification for printing the subarray with the maximum sum involves tracking the start and end indices of the subarray when the sum exceeds the maximum, without affecting the time complexity.', 'The video content is suggested as an essential resource for understanding the algorithm, emphasizing its relevance to subsequent problems in the series.']}], 'duration': 434.679, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/AHZpyENo7k4/pics/AHZpyENo7k4764697.jpg', 'highlights': ['The pronounced algorithm states that by continuously adding and drawing when the sum goes below 0, the maximum subarray sum can be found as 7.', 'The algorithm computes the maximum subarray sum by iterating through the array and updating the sum, re-initializing it to 0 if it becomes negative, and updating the maximum if the current sum exceeds it.', 'The modification for printing the subarray with the maximum sum involves tracking the start and end indices of the subarray when the sum exceeds the maximum, without affecting the time complexity.', 'The result of finding the maximum subarray sum is 7.', 'The video content is suggested as an essential resource for understanding the algorithm, emphasizing its relevance to subsequent problems in the series.']}], 'highlights': ['The Stribers A2Z DSA course comprises 455 modules, and students would have solved more than 400+ problems in DS Algo by the end of the course.', "The course provides the world's most in-depth training in DS Algo, surpassing any paid courses available online.", 'Completing the entire course guarantees proficiency in clearing DS algorithms in any company worldwide.', 'The process involves iterating through all the subarrays of the given array to find the maximum sum, with each iteration involving three loops, resulting in a time complexity of approximately O(n^3)', 'The space complexity of the brute force solution is O(1), as it does not require any additional space for computation', 'The pronounced algorithm states that by continuously adding and drawing when the sum goes below 0, the maximum subarray sum can be found as 7.', 'The modification for printing the subarray with the maximum sum involves tracking the start and end indices of the subarray when the sum exceeds the maximum, without affecting the time complexity.', "The chapter introduces Kadane's algorithm for finding the most optimal solution in an array, emphasizing the thought process and decision-making for selecting subarrays to maximize the sum.", 'The algorithm involves starting with a maximum set to the lowest number, iterating through the array, and updating the maximum when a better sum is encountered, showcasing a step-by-step thought process for selecting subarrays to maximize the sum.', 'The explanation emphasizes the importance of neglecting negative sums to enhance the overall result, as carrying negative sums forward will always reduce the summation, and only positive sums contribute to increasing the overall sum.']}