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
Tag Archives: dynamic programming
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].
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.