Участник:Бушенкова Ксения/LeetCode Pizza With 3n Slices

Материал из DISCOPAL
Перейти к: навигация, поиск

Бушенкова Ксения 17:56, 24 мая 2020 (MSK) https://leetcode.com/problems/pizza-with-3n-slices/

class Solution {
    public int maxSizeSlices(int[] slices) {
    	int n = slices.length;
    	if(n == 1){
    		return slices[0];
    	}
    	if(n == 2){
    		return Math.max(slices[0], slices[1]);
    	}
 
    	return Math.max(maxSizeSlices(slices, 0, n - 2, n / 3), maxSizeSlices(slices, 1, n - 1, n / 3));
    }
 
    int maxSizeSlices(int[] slices, int start, int end, int k) {
    	int n = end - start + 1;
    	int[][] dp = new int[n + 1][k + 1];
    	dp[1][1] = slices[start];
    	for(int i = 2; i <= n; i++){
    		for(int j = 1; j <= k; j++){
    			dp[i][j] = Math.max(dp[i - 1][j], dp[i - 2][j - 1] + slices[i + start - 1]);
    		}
    	}
    	// System.out.println(Arrays.deepToString(dp));
    	return dp[n][k];
    }
 
 
}