Участник:Бушенкова Ксения/LeetCode Pizza With 3n Slices — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «~~~~ https://leetcode.com/problems/pizza-with-3n-slices/ class Solution { public int maxSizeSlices(int[] slices) { int n = slices.length; if(n ==…»)
 
(Массовая правка: удаление Категория:На проверку)
 
(не показана 1 промежуточная версия 1 участника)
Строка 2: Строка 2:
 
https://leetcode.com/problems/pizza-with-3n-slices/
 
https://leetcode.com/problems/pizza-with-3n-slices/
  
 
+
<code-java>
 
class Solution {
 
class Solution {
 
     public int maxSizeSlices(int[] slices) {
 
     public int maxSizeSlices(int[] slices) {
Строка 32: Строка 32:
 
}
 
}
  
[[Категория:На проверку]]
+
</code-java>

Текущая версия на 13:16, 25 мая 2020

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