Code Forum

Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle . A sub-rectangle is any contiguous sub-array of size or greater located within the whole array. As an example, the maximal sub-rectangle of the array: is in the lower-left-hand corner: and has the sum of 15.

Write a function to generate all possible n pairs of balanced parentheses. For example, if n=1 {} for n=2 {}{} {{}}

Two people want to send coded messages to each other. One possible encoding scheme is to simply replace each letter with its numerical value in the alphabet and then string all the digits together without spaces. Determine the number of possible ways to decode a message encoded this way. eg: the message encoded as 25114 can be decoded as BEAAD, BEAN, YAD, YAN, ‘YKD’ and ‘BEKD’, so there are 6 different decoding of given string value.

Variation of LIS: Given an integer array, how will you find out the increasing subsequence which gives the largest sum. For example, 50,23,1,67,30 in this subsequence a few possible increasing subsequences are 1)    23,30 2)    23,67 2)    50,67 3)    1,67 4)    1,30 5)    67 6)    30 but 50, 67 gives the maximum sum. How to find it Note: In the above scenario however if we have 128 at index 0 then it will have the max sum although it is not forming longest LIS.

Given 1, 2, 5, and 10 paise coins, how many ways can you make a rupee? Hint: Order doesn't matter.

On a positive integer, you can perform any one of the following 3 operations. 1.) Subtract 1 from it. ( n = n - 1 )  2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2) 3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3  ). Now given a positive integer n , find the minimum number of steps that takes n to 1

Given an integer array  sequence , return the  length  of the longest increasing subsequence (LIS)  A longest increasing subsequence is defined as a subsequence in the given sequence of integers such that the elements in the subsequence are in sorted order, lowest to highest and in which the subsequence is as long as possible  Sample Test Cases:   Input #00:  1, 2, 3 Output: 3 Explanation: The sequence in itself is an increasing one  Input #01:   4, 5, 6, 7, 8, 1, 2, 1, 2, 3, 5, 4, 6, 7, 8, 9, 0, 6, 7 Output #01: 8 Explanation:   The length of the LIS is 8. The LIS elements from the sequence are highlighted: 4, 5, 6, 7, 8, 1, 2, 1, 2, 3, 5 , 4,  6,7, 8, 9 , 0, 6, 7

Given a list of 3 coins, their values (1,3,5), and the total sum 11. Find the minimum number of coins the sum of which is 11 (we can use as many coins of one type as we want). Hint: use dynamic programming