Maximum sum contiguous sub-array
Posted onFind a contiguous sub-array whose sum is maximum. Using the dynamic programming based Kadane’s Algorithm, we can solve this in O(N) time.
Tag: Dynamic Programming
Dynamic Programming – Edit Distance
Posted onHello people..! In this post, we will see another dynamic programming based problem, finding the minimum edit distance between two strings. Problem – Given two strings A and B, we need to find the minimum number of operations which can be applied on A to convert it to B. The operations are – Edit – Change a […]
Dynamic Programming – Kadane’s Algorithm
Posted onHello people..! In this post, we will look at a simple dynamic programming based algorithm which is the optimal solution to the Maximum Sum Subarray Problem. Try to focus on how the approach of dynamic programming is applied rather than just trying to understand the main algorithm. Now, let us define the problem. Maximum Sum […]
Dynamic Programming – Introduction and Fibonacci Numbers
Posted onNote – Theory of Programming is shifting to YouTube! This post has a video. Watch it at – https://youtu.be/rOjPwES9R2k Hoping you’ll support the YouTube channel just like you have greatly supported the website! 🙂 Hello people..! This is the first post of Dynamic Programming – Introduction and Fibonacci Numbers. In this post I will introduce […]