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

Материал из DISCOPAL
< Участник:Бушенкова Ксения
Версия от 17:56, 24 мая 2020; Бушенкова Ксения (обсуждение | вклад) (Новая страница: «~~~~ https://leetcode.com/problems/pizza-with-3n-slices/ class Solution { public int maxSizeSlices(int[] slices) { int n = slices.length; if(n ==…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Бушенкова Ксения 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];
   }


}