Untitled

mail@pastecode.io avatar
unknown
plain_text
13 days ago
775 B
2
Indexable
Never
int solution(int n, int[] prices) {
        int[] dp = new int[n + 1];
        
        // Initialize dp array to store the maximum revenue for each length
        for (int i = 0; i <= n; i++) {
            dp[i] = 0;
        }
        
        // Iterate for each length of rod from 1 to n
        for (int i = 1; i <= n; i++) {
            int maxVal = Integer.MIN_VALUE;
            
            // Try every possible cut of the rod of length i
            for (int j = 1; j <= i; j++) {
                maxVal = Math.max(maxVal, prices[j] + dp[i - j]);
            }
            
            // Store the maximum revenue for length i
            dp[i] = maxVal;
        }
        
        // The maximum revenue for length n is stored in dp[n]
        return dp[n];
    }
Leave a Comment