Algorithm: Leetcode Contest 397

3147. Taking Maximum Energy From the Mystic Dungeon

Solution

class Solution {
    public int maximumEnergy(int[] energy, int k) {
        // brute force: traverse all possible start
        
        int res = Integer.MIN_VALUE;

        for(int i = 0; i <= k; i++) {
            res = Math.max(res, getSum(i, energy, k));
        }
        
        return res;
    }
    
    // kth start
    private int getSum(int start, int[] energy, int k) {
        int i = start;
        int sum = 0;
        while(i < energy.length) {
            if (sum < 0) {
                sum = 0;
            }
            sum += energy[i];
            
            i += k;
        }
        
        return sum;
    }
}

Retro

this problem can easily get TLE if traverse all index, but actually the k step implies the array can be split into k sub-arrays then we just need to calculate the max value of sub array.

cannot resolve the remaining tasks..