Algorithms Lecture 13: Maximum Sub-array Problem using Divide-and-Conquer
Vložit
- čas přidán 4. 01. 2019
- California State University, Sacramento
Spring 2018
Algorithms
by Ghassan Shobaki
Text book: Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, 3rd Edition, MIT Press, Cambridge (2009)
Note: There is a dynamic programming algorithm (Kadane's algorithm) that solves this problem in linear time, but it is not discussed here. This lecture is limited to the divide-and-conquer algorithm.
Correction:
Line 3 in the pseudo-code (written at Minute 13) should be
L = MaxSubarray(A, p, q)
The third parameter should be q not q-1
MaxCrossingSubarray(A, p, q, r)
leftSum = -∞
sum = 0
for i = q down to p
sum = sum + A[i]
if sum Greater than leftSum
leftSum = sum
rightSum = -∞
sum = 0
for j = q+1 to r
sum = sum + A[j]
if sum Greater than rightSum
rightSum = sum
return leftSum + rightSum
Finally found the video clearly explains maximum Sub-array problem using Divide-and-Conquer! Really appreciate!
x2
I understood the Kadane's Algorithm but was struggling in divide and conquer solution. This video cleared all my doubts. Thanks, Professor!!
Thanks professor for this valuable lecture.
And Guys here is the full solution----First try out with yourself and do let me knw if u have any problem in solving programming problems
class Solution {
public int maxSubArray(int[] a) {
return max_sum_array_recursion(a, 0, a.length-1);
}
private static int max_sum_array_recursion(int[] a, int i, int j) {
if(i==j)return a[i];
int middle= (i+j)/2;
int L= max_sum_array_recursion(a,i,middle);
int R= max_sum_array_recursion(a,middle+1,j);
int C = findMaxCrossing(a,i,j,middle);
return Math.max(Math.max(L, R),C);
}
static int findMaxCrossing(int[] arr, int startIndex, int endIndex, int mid) {
int maxLeftSum = arr[mid];
int currentSum = maxLeftSum;
for (int i = mid - 1; i >= startIndex; i--) {
currentSum += arr[i];
maxLeftSum = Math.max(maxLeftSum, currentSum);
}
int maxRightSum = arr[mid + 1];
currentSum = maxRightSum;
for (int i = mid + 2; i
This is the best video for understanding maximum subarray sum using divide and conquer. Thank you sir :)
Thanks Ghassan Shobaki, great stuff!
Have seen many videos on the same problem. Though, it doesn't introduced the Kadane's algo, but divide and conquer explanation is just superb. Much appreciated! Thank you :)
helped me a lot. your teaching method is excellent
Thank Professor, now i understand the Divide and Conquer solution.
This is actually so good. Thanks, man.
Awesome
Awesome explanation... Please have the bright light so that we can read everything clearly and it looks good.
finally sir, thank you so much I had understood this problem so perfectly
best explanation on this topic. seriously. thanks
Much better than Cormen's explanation. Thank you, professor Ghassan :)
Cormen's book is more like a puzzle :-)
Thank you so much'. Best video on divide and conquer
Thanks for clarifying this question :)
The explanation is good but i think if you had given an example while making the recurrence tree for a small problem it would have been really amazing.
Awesome explanation.
Excellent teacher!
Great explanation!
wow, thank you Professor
Explanation was Priceless !
The Psuedocode needs to modified a bit
private static int maxSubArrayInternal(int[] nums, int start, int end) {
if (start == end) {
return nums[start];
}
int mid = (start+(end-start)/2);
int left = maxSubArrayInternal(nums, start, mid);
int right = maxSubArrayInternal(nums, mid+1, end);
int crossingSum = maxSubArrayCrossing(nums, start, mid, end);
return Math.max(left, Math.max(right, crossingSum));
}
fantastic lecture. thank you.
Finally understood... Thank you
why do i get different results if i start to sum my left subarray in my max_cross_sum function from start then incrementing instead of mid then decrementing?
for example: if i sum left subarray starting from middle then decrementing, i get with the example from the lecture {-1, 3, 4, -5, 9, -2}->11 which is correct, but if i left sum from start then increment with the same example i get a 10,
my question is how is my own implementation wrong? its the same implementation i just decided to operate on the array from the other end.
I was able to understand this easily than how it was explained in the book.
Awesome explanation !! Cleared all the prior confusions . Thanks, Professor !
awesome explanation sir, and this how we should be taught in our college instead of where no classes are taken
This is Univ. of California - how can you expect your tier 3 clg in India turn into this 🤣
thank you sir, extremely helpful
Interesting, so the best way to use Divide and Conquer is to find the least amount of sub-problems to solve. In this case is 2, however in the quick sort algorithm we find the smallest sub-problem.
Thanks for not writing the maximumCrossingSubarray very helpful
The MaxCrossingSubarray code has been added to the video's Description field.
thank you professor
Thank you : )
Thanks🙏🏻
Finally I've get to know the crossing sum in divide and conquer approach.
I think when we go left it will be T(logn) instead of T(n/2) and for every left and right we do T(n) for centre so the overall time would be T(nlogn) which is merge sort, please correct here if wrong.
No, it will be T(n/2) because we have divided the space into half, the problem is still the same. The overall time complexity will surely come as nlogn.
please add more lights in room
Once I know the MaxLeft and the MathRight, I can add both values to get the MaxCrossing value. So in the end I just need to return the max value of those 3
Like this:
public static int maxSubArrayDivideAndConquer(int A[]) {
int n = A.length;
if (n == 0)
return 0;
return maxSubArrayHelperFunction(A, 0, n - 1);
}
public static int maxSubArrayHelperFunction(int A[], int left, int right) {
if (right == left)
return A[left];
int middle = (left + right) / 2;
int leftans = maxSubArrayHelperFunction(A, left, middle);
int rightans = maxSubArrayHelperFunction(A, middle + 1, right);
int leftmax = A[middle];
int rightmax = A[middle + 1];
int temp = 0;
for (int i = middle; i >= left; i--) {
temp += A[i];
if (temp > leftmax)
leftmax = temp;
}
temp = 0;
for (int i = middle + 1; i rightmax)
rightmax = temp;
}
return Math.max(Math.max(leftans, rightans), leftmax + rightmax);
}
May I know what does p and r indicate as? Sorry for asking dumb questions
As defined in the earlier lectures on divide-and-conquer, p is the start index and r is the end index of the input array.
greetings to our egyption professor🎓🎓
MaxCrossingSubarray function, does it need at most (q-p+1) sum and comparations plus (r-q+1) sum and comparations?
it seems the computation cost is high
The computation cost for the MaxCrossingSubarray is clearly linear
@@ghassanshobakicomputerscie9478
I thought you were speak on gematria. I must have clicked on the wrong video.
Nice explanation though. Thank you.
thanks
Is it "L = MaxSubarray(A, p, q - 1)" OR "L = MaxSubarray(A, p, q)"? Isn't L from 0 to q (not q-1), and R from q+1 to r?
You are right. L is from p to q and R is from q+1 to r. No element is skipped. Please note that there is a correction in the Description section.
algorithm has mistake
the correction is
R=maxsubarray(A,q,r)
Please see the correction posted in the Description field.
4:54
Thanks a lot!
Finally Yeahhhh
It is a very good lecture. Still I get some doubts. At 3.23-3.27, he tells the solution is the index range which gives the max. sub array value. But while writing algorithm, the output is the value of the max. subarray (max{L,C,R}). Also in algo, q-1 should be q; It should be a typo. Otherwise, every time, you cut the middle element from the array. To calculate C one time, I agree the time complexity is O(n) obviously. But is not we find C recursively everytime we divide and as the height is log n, is not that n*logn time we calculate C value?
You are right about both points.
A complete and useful implementation should return the indices not just the value. In the pseudo-code given here, we return the value for simplicity. Returning the indices requires tracking indices and that would make the pseudo-code unnecessarily messy. I make a note about this at 15:00.
The index on Line 3 should be q not q-1 and this correction is noted in the description.
@@ghassanshobakicomputerscie9478 many thanks for your kind reply. This max_subarray was a nice video explanation of yours sir If you have other videos on algo., I would be happy to watch and learn.
Here is the link to the Algorithms playlist:
czcams.com/play/PL6KMWPQP_DM8t5pQmuLlarpmVc47DVXWd.html
what is p and r ? about 12:20
starting index and last index respectively
This can be solved by sliding window
U could’ve just use O(n) with a queue
But is that the divide-and-conquer way?
that code at the end is wrong. How does it sum up the sub-array values? no addition at all.
The summation is inside the MaxCrossingSubarray function, for which the code is not shown
@@ghassanshobakicomputerscie9478 can you please show it now ! Because I want to learn and was not able to find.
@@shreevatsalamborghin here is a java implementation:
static int findMaxCrossing(int[] arr, int startIndex, int endIndex, int mid) {
int maxLeftSum = arr[mid];
int currentSum = maxLeftSum;
for (int i = mid - 1; i >= startIndex; i--) {
currentSum += arr[i];
maxLeftSum = Math.max(maxLeftSum, currentSum);
}
int maxRightSum = arr[mid + 1];
currentSum = maxRightSum;
for (int i = mid + 2; i
Surya Valiveti Dhanyavad
There's a solution faster than this with divide and conquer.
Why bother talking about an O(nlogn) solution when a simpler O(n) solution exists?
Because this algorithm is a very good example of the divide-and-conquer method
Just to clear basics
Why bother looking at video titled "... Divide-and-Conquer" if you don't want to learn about it?
this is a very good example of divide and conquer approach, you can solve alot of array related problems and achieve a not bad time complexity O(nlogn) instead of something like o(n^2), if you debug the code and understand how recursion/this algorithm works, you can later use the same concept on a different problem