Algorithms Lecture 13: Maximum Sub-array Problem using Divide-and-Conquer
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
Видео Algorithms Lecture 13: Maximum Sub-array Problem using Divide-and-Conquer канала Ghassan Shobaki Computer Science Lectures
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
Видео Algorithms Lecture 13: Maximum Sub-array Problem using Divide-and-Conquer канала Ghassan Shobaki Computer Science Lectures
Показать
Комментарии отсутствуют
Информация о видео
6 января 2019 г. 6:26:34
00:18:40
Другие видео канала
![Kadane's Algorithm - Maximum Sum Subarray (Amazon Coding Interview Question)](https://i.ytimg.com/vi/jnoVtCKECmQ/default.jpg)
![Finding Maximum Sum SubArray using Divide and Conquer Approach.](https://i.ytimg.com/vi/3GD-3UZGsVI/default.jpg)
![2 Divide And Conquer](https://i.ytimg.com/vi/2Rr2tW9zvRg/default.jpg)
![Advanced Algorithms (COMPSCI 224), Lecture 1](https://i.ytimg.com/vi/0JUN9aDxVmI/default.jpg)
![Kadane's Algorithm to Maximum Sum Subarray Problem](https://i.ytimg.com/vi/86CQq3pKSUw/default.jpg)
![3. Divide & Conquer: FFT](https://i.ytimg.com/vi/iTMn0Kt18tg/default.jpg)
![Algorithms Lecture 19: Dynamic Programming, Longest Common Subsequence and Longest Common Substring](https://i.ytimg.com/vi/L1fUKbgyAk4/default.jpg)
![(Remade) Maximum Sum Subarray | Kadane's Algo | Divide And Conquer | Leetcode 53](https://i.ytimg.com/vi/Eo2wQIPSwrw/default.jpg)
![Algorithms Lecture 6: Solving Recurrences Using the Recursion Tree Method](https://i.ytimg.com/vi/k_fuglZ1km8/default.jpg)
![Max Contiguous Subarray Sum - Cubic Time To Kadane's Algorithm ("Maximum Subarray" on LeetCode)](https://i.ytimg.com/vi/2MmGzdiKR9Y/default.jpg)
![LeetCode Challenge Day 3 - Max Subarray](https://i.ytimg.com/vi/umt7t1_X8Rc/default.jpg)
![Divide & Conquer (Think Like a Programmer)](https://i.ytimg.com/vi/11V7Ik0IBHU/default.jpg)
![Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python](https://i.ytimg.com/vi/5WZl3MMT0Eg/default.jpg)
![Acing Google Coding Interview as an 18 year old High School Student](https://i.ytimg.com/vi/-tNMxwWSN_M/default.jpg)
![13. Learning: Genetic Algorithms](https://i.ytimg.com/vi/kHyNqSnzP8Y/default.jpg)
![Algorithms Lecture 1: Introduction (The Role of Algorithms)](https://i.ytimg.com/vi/yRWybIkHL98/default.jpg)
![Algorithms Lecture 16: Greedy Algorithms, Proofs of Correctness](https://i.ytimg.com/vi/XXBjf-7FmfI/default.jpg)
![Maximum sum sub-array](https://i.ytimg.com/vi/ohHWQf1HDfU/default.jpg)
![Maximum Sum SubArray (Kadane's algorithm) (Largest Sum Contigous SubArray)](https://i.ytimg.com/vi/kekmCQXYwQ0/default.jpg)
![Greedy Stays Ahead (Algorithms 08)](https://i.ytimg.com/vi/WAf5fop1EZg/default.jpg)