Compound interest with varying compounding frequency Here is the problem I have attempted to solve.


  Given original principal $n$ and aggregate rate $r$, find the maximum final principal that can be yielded.


Though I know that the higher the compounding frequency is, the higher the final principal will be, a special condition applies:


  Intermediate principals are rounded down to the the nearest integer each time.


So for example $n = 10000$ and $r = 3$, I can choose to have


1% growth 3 times
a 2% growth then a 1% growth
or a 3% growth.


For case 1 n would grow as 10000 -> 10100 -> 10201 -> 10303.

For case 2 n would grow as 10000 -> 10200 -> 10302.

For case 3 n would grow as 10000 -> 10300.

So in this case the highest value would be 10303.

As another example, take $n = 10$ and $r = 10$. As it will not yield any changes to $n$ unless the growth rate is higher than 10%, the answer is 11.

So in mathematical terms it is to find $\max n\prod(1+r_i\%)$ where $\sum r_i = r$ with the rounding condition.

What I was trying to do is to find the minimum growth rate that would result in a change in $n$ and apply it immediately, then repeat the process until $r$ is used up, but it doesn't seem that it is getting the desired answer. Any hints would be appreciated. If you need any clarification please tell me.

    while(r &gt; 0 &amp;&amp; rate &lt; r){
        rate++;
        if (n * (100 + rate) / 100 != n){
            n = n * (100 + rate) / 100;
            r -= rate;
            rate = 0;
        }
    }


$r_i$ must be positive integers.
This problem is adapted from A028:武器の強化 problem, which can be found here (on paiza, which is a Japanese-language coding contest site).
This problem is a good example of problems that can be solved by dynamic programming.

Given original principal $n$, the subproblems are, what is $p(t)$ for $0\le t\le r$, the maximum final principal that can be yielded if aggregate rate is $t$ . We have the following recurrence relation, where $//$ means the integer division, for example, $13 \operatorname{//} 5 = 2$. 

$$p(t) = \max( p(0) + p(0)* t \operatorname{//} 100,\ p(1)+p(1) * (t-1) \operatorname{//} 100,\ p(2)+ p(2) * (t-2) \operatorname{//}100,\ \cdots,\ p(t-1)+ p(t-1) * 1 \operatorname{//} 100)
$$

From $p(0)=p$ you can compute $p(1)$. From $p(0)$ and $p(1)$, you can compute $p(2)$. And so on. Finally you can will get $p(r)$, which is what you want.

I will left you figure out the actual implementation. By the way, the code in question, fails when the original principal is 23 and the aggregate rate r is 9.