NiNi's Den

Word count: 443Reading time: 3 min
2017/11/15 Share

Continue…

##### 3. Given an integer (not necessary a decimal number) with n digits, we want to remove $m (\le n)$ digits from this number such that the resulting number is as large as possibe. Design an $O(n)$ time algorithm to solve it.

Example :
n = 5612398752 (decimal)
When m = 2, answer should 62398752
When m = 3, answer should be 6398752
It’s easy to find out that we should care about most significant digit.

Algorithm :

##### 10. Given a 2-dimensional nn matrix M of real numbers, design an efficient algorithm to find a sub-rectangle such that the sum of the numbers in it is maximal over all sub-rectangles of M. Here, each sub-rectangle is an n1n2 (1 n1, n2  n) matrix with consecutive indices of rows and columns.

#####11. Given a sequence of integers, and k another integer, design an algorithm to find a substring such that the sum of the numbers in it is exactly k if there does exist such a substring.

Original Author: Terrynini