Tag Archives: dynamic programming

Sliding window min/max – Dynamic Programming

Given an array of integer A[] and the size of sliding window w. Assume that the window of size w starting from left keeps sliding by moving the window one element to right each time. Find the stream of sliding minimums in optimal way. A sliding minimum is the minimum element of current window. Let’s […]

Max sum subsequence with non-consecutive elements – Kadane’s Algorithm (DP)

Given an array of integer. Find the maximum sum subsequence such that elements are not consecutive. For example, A = [−2, 1, −3, 4, −1, 2, 1, −5, 4] then max sum=11 with the subarray [1, 4, 2, 4]. First of all, lets solve the problem with less constraint. Suppose we need to find out […]

Longest palindromic substring in linear time

Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string For example, longest palindromic substring of S = “babaabca” is “baab”. In a previous post I described a simple O(n^2) time solution for this problem. But there is a very beautiful […]

Longest palindromic substring in linear time

Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string For example, longest palindromic substring of S = “babaabca” is “baab”. In a previous post I described a simple O(n^2) time solution for this problem. But there is a very beautiful […]