How to find the maximum compound rate in a candlestick serie?

I want to find the maximum compound interest rate in a candlestick serie.

The difficulty here is to find the best next "HIGH" value in a serie which will not bypass a possible intermediate additional interest in between.

For example, four OHLCs (time, open, high, low, close) with such values to test.

Useless values have been set to zero to ease the reading.

(time, open, high, low, close)
[ 3,    0,    2,    0,    0 ]
[ 2,    0,    0,    1.8,  0 ]
[ 1,    0,    1.1,  0,    0 ]
[ 0,    0,    0,    1,    0 ]

If I do a simple iteration on every ohlc from oldest to latest to find it's next higher "HIGH" value in the OHLC serie :

ohlcs.stream().filter(nextOhlc -> 
    nextOhlc.getTime() > currentOhlc.getTime() 
    && nextOhlc.getHigh().compareTo(currentOhlc.getLow()) > 0
).findFirst()

It will compute interest of ohlc[0].low value with ohlc[1].high value and ohlc[2].low value with ohlc[3].high, giving a compound rate of ~1.22.

Whereas the computation should choose to compute ohlc[0].low with ohlc[3].high, giving a compound rate of 2.

Should I compute every possibilities of the serie to find the best one (something like n^ⁿ possiblities with n OHLCs) ?

There must be a simpler way to find to maximum compound interest rate over a candlestick serie.

Thanks for helping.

Solution

With some constraint I exchange with you, I will provide you a DP alogirthm with complexity is O(n^2).

First, I reverse array and remove the redundant field, 2 field left are high and low.

Make the test data:

Ohlc[] ohlcList = new Ohlc[]{
        new Ohlc(7, 2), // time = 0
        new Ohlc(10, 2), // time = 1
        new Ohlc(4, 1), // time = 2
        new Ohlc(4, 1), // time = 3
        new Ohlc(2, 1), // time = 4
        new Ohlc(2, 1), // time = 5
        new Ohlc(5, 3), // time = 6
        new Ohlc(9, 3), // time = 7
        new Ohlc(6, 2) // time = 8
};

double[] dp = new double[ohlcList.length];

With dp[i] meaning result of the sub problem end at i (must end at i), that mean the last ohlc we choose is ohlcList[i].high

// the base case
dp[0] = 0
dp[1] = ohlcList[1].high / ohlcList[0].low

The constraint about dp[i] and sub problem is:

dp[i] = max(dp[j - 1] * (ohlcList[i].high / ohlcList[j].low) with 0 <= j < i.

And result is max value of array dp.

Here is the complete code:

public class Main {

    public static void main(String[] args) {
        Ohlc[] ohlcList = new Ohlc[]{
                new Ohlc(7, 2), //0
                new Ohlc(10, 2), // 1
                new Ohlc(4, 1), // 2
                new Ohlc(4, 1), // 3
                new Ohlc(2, 1), // 4
                new Ohlc(2, 1), // 5
                new Ohlc(5, 3), // 6
                new Ohlc(9, 3), // 7
                new Ohlc(6, 2) // 8
        };

        double[] dp = new double[ohlcList.length];
        dp[0] = 1.0;
        dp[1] = ohlcList[1].high / ohlcList[0].low;
        for (int i = 2; i < ohlcList.length; i++) {
            dp[i] = ohlcList[i].high / ohlcList[0].low;
            for (int j = 1; j < i; j++) {
                dp[i] = max(dp[j - 1] * (ohlcList[i].high / ohlcList[j].low), dp[i]);
            }
        }
        System.out.println(Arrays.stream(dp).max().getAsDouble());
    }

    @Data
    @AllArgsConstructor
    static
    class Ohlc {
        double high;
        double low;
    }
}