Tag Archives: Dynamic Programming

Question: Write a program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

We need to focus on the fact that whenever sum of digits of array goes less than zero it is better to keep the sum as 0. Anywhere we’ll encounter a positive integer we’ll again start the sum.

Example:

array : -2 -3 4 -1 -2 1 5 -3

sum  :  0 0 4 3 1 2 7 4

So 7 is the result.

Code:

Filed under Algorithms

Dynamic Programming – Famous coin sum question

Question: Out of given ‘N’ coins, give the minimum number of coins required to sum upto ‘S’

(Assumption: list of coins is sorted)

Loop from 1 to S and check solution for each denomination keeping solution for 0 as 0. DYNAMIC PROGRAMMING !!

For example, if you have N coins as {1, 3, 5} and you have to sum upto 10 then loop from 1 to 10 and for each number check if the number is more than maximum value of denomination present. If yes, than your answer will be (number – maximum denomination)’s answer + 1.

Number — COINS REQUIRED

0 — 0

1 — 1

2 — 2  (i.e. [2-1]’s answer + 1 i.e. [1]’s answer + 1 i.e. 1 + 1 == 2)

3 — 3  (i.e. [3-3]’s answer + 1 i.e. [0]’s answer + 1 i.e. 0 + 1 == 1)

4 — 2

5 — 1

and so on…

10 — 2  (you know why !)

Code: