\n# Approach\nThe solve_space_opti function takes the input vector slices and calculates the maximum sum of non-adjacent elements.\n\nIt starts by initializing vectors prev1, curr1, and next1 with size k+2, where k is the size of slices. These vectors will be used to store the maximum sums at each level.\n\nIt then enters a loop from index = k-2 to index >= 0, iterating over the elements of slices from the second-to-last element to the first element.\n\nInside the loop, another loop iterates from n = 1 to n <= k/3, representing the number of non-adjacent elements to consider.\n\nFor each index and n, it calculates two possibilities:\n\ntake: The sum of the current slice (slices[index]) and the maximum sum of non-adjacent elements for the remaining slices starting from index+2. This is calculated by adding next1[n-1] to the current slice.\nnottake: The maximum sum of non-adjacent elements for the remaining slices starting from index+1. This is calculated by taking curr1[n].\nThe maximum sum for the current state is then determined as max(take, nottake), and stored in the prev1 vector at index n.\n\nAfter each iteration, the next1 vector is updated with the values of curr1, and curr1 is updated with the values of prev1.\n\nOnce the first loop completes, it calculates case1 as the maximum sum of non-adjacent elements for the first k/3 slices using curr1[k/3].\n\nIt then enters another loop from index = k-1 to index >= 1, iterating over the elements of slices from the last element to the second element.\n\nInside the loop, the same process is repeated as in step 5, but using different vectors prev2, curr2, and next2.\n\nOnce the second loop completes, it calculates case2 as the maximum sum of non-adjacent elements for the last k/3 slices using curr2[k/3].\n\nFinally, it returns the maximum value between case1 and case2, representing the overall maximum sum of non-adjacent elements.\n\n# Complexity\n- Time complexity:0(K*K)\n\n\n- Space complexity:0(k)\n\n\n# Code\n```\nclass Solution {\npublic:\n\nint solve_space_opti(vector slices)\n{\n int k = slices.size();\n vectorprev1(k+2,0);\n vectorcurr1(k+2,0);\n vectornext1(k+2,0);\n\n vectorprev2(k+2,0);\n vectorcurr2(k+2,0);\n vectornext2(k+2,0);\n\n for(int index = k-2;index >=0;index--)\n {\n for(int n = 1;n<=k/3;n++)\n {\n int take = slices[index] + next1[n-1];\n int nottake = 0 + curr1[n];\n prev1[n]= max(take,nottake);\n }\n next1=curr1;\n curr1=prev1;\n }\n int case1=curr1[k/3];\n\n for(int index = k-1;index>=1;index--)\n {\n for(int n = 1;n<=k/3;n++)\n {\n int take = slices[index] + next2[n-1];\n int nottake = 0 + curr2[n];\n prev2[n]= max(take,nottake);\n }\n next2=curr2;\n curr2=prev2;\n }\n int case2=curr2[k/3];\n\n return max(case1,case2);\n\n}\n int maxSizeSlices(vector& slices) {\n return solve_space_opti(slices);\n }\n};\n```\n\n# Approach\nThe solve function is a recursive helper function that calculates the maximum sum of non-adjacent elements in the slices array. It takes the following parameters:\n\nindex: The current index being considered.\nendindex: The last index in the current subarray being considered.\nslices: The array of slices.\nn: The number of non-adjacent elements to consider.\ndp: A 2D memoization table to store already calculated values.\nThe base cases for the recursion are:\n\nIf n is 0 (no more non-adjacent elements to consider), or index exceeds endindex, return 0.\nIf the value for the current state (dp[index][n]) is already calculated, return it.\nThe function calculates two possibilities:\n\ntake: The sum of the current slice (slices[index]) and the maximum sum of non-adjacent elements for the remaining slices starting from index+2. This is calculated recursively by calling solve(index+2, endindex, slices, n-1, dp).\nnottake: The maximum sum of non-adjacent elements for the remaining slices starting from index+1. This is calculated recursively by calling solve(index+1, endindex, slices, n, dp).\nThe maximum sum for the current state is then determined as max(take, nottake), and stored in the memoization table dp[index][n].\n\nThe maxSizeSlices function is the main function that takes the input vector slices and performs the following steps:\n\nInitializes two memoization tables dp1 and dp2 of size kxk with -1.\nCalls the solve function twice:\nFor case1, it considers the slices starting from index 0 and ending at k-2, and aims to select k/3 non-adjacent elements.\nFor case2, it considers the slices starting from index 1 and ending at k-1, and aims to select k/3 non-adjacent elements.\nReturns the maximum value between case1 and case2.\n\n# Complexity\n- Time complexity:0(K*K)\n\n\n- Space complexity:0(k*k)\n\n\n# Code\n```\nclass Solution {\npublic:\n\n\nint solve(int index,int endindex,vector& slices,int n ,vector>&dp)\n{\n if (n==0 || index>endindex)\n {\n return 0;\n }\n if(dp[index][n]!=-1 ){\n return dp[index][n];\n }\n int take = slices[index] + solve(index+2,endindex,slices,n-1,dp) ;\n int nottake = solve(index+1,endindex,slices,n,dp);\n return dp[index][n]= max(take,nottake);\n}\n\n\n\n\n int maxSizeSlices(vector& slices) {\n int k = slices.size();\n vector> dp1(k,vector(k,-1));\n int case1=solve(0, k-2, slices, k/3,dp1);\n vector> dp2(k,vector(k,-1));\n int case2=solve(1, k-1, slices, k/3,dp2);\n return max(case1,case2);\n }\n};\n```

Pizza With 3n Slices

Problem Description

Problem Description

Answer Panel