Close

Longest sub array with zero sum

Given an array of integers (positive and negative), how do we find a longest sub-array with zero sum? For example, consider the example [5, 0, -1, 3, -2, 4], the longest sub array with zero sum contains 4 elements.  The straight forward approach is to check the sum of all possible arrays and find out…

Longest common subsequence problem

This is a famous computer science problem with various applications in tools such as file diff, bio informatics etc. For more information read this on wiki. Given a set of strings, how do we find the longest common sub-sequence(LCS) among them? For example, LCS{“ATDACG”,”CTDACGA”} is  “TAG”. In this post, we will look at the algorithm…

Minimum coin change problem

Given a set of denominations and an amount, how do we minimize the number of coins to make up the given amount? Let us consider the set of denominations {1,3,4}. Also assume that we have infinite supply of coins for each denomination. To make change for 6, we can have three combinations {1,1,4} {1,1,1,3} {3,3}…

Subset sum problem

Given a set of numbers and a target value, we have to find if there is any subset whose sum is equal to the target value. For example let the array be {10, 34, 19, 27, 58, 45} and the target sum is 56, we have a subset {10,19,27} with the given sum. We don’t…

Maximum sum sub-array

Given an array of positive and negative values. We have to find the maximum sum a sub-array can have. For example the the array {-1, 7, -2, 4, -3, -9, 2} has a maximum sum of 9 which corresponds to the sub-array {7, -2, 4}. To solve this problem, we take two variables to keep…