Tag Archives: kadane

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 Valid Parenthesis

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring. For “(()”, the longest valid parentheses substring is “()”, which has length = 2. Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4. First look at the […]