# Help me to solve my coding interview question

The following task can be performed on an array of integers:
1.Choose a subarray of arr of size 1 at most x times.
2.Choose a subarray of arr of size 2 at most y times.
3.Choose a subaray of arr of size 3 at most z times.
The chosen subarrays should benon-overlapping. The profit is calculated as the sum of the elements in the chosen subarrays. What is the maxximum profit that can be obtained?
For example,
consider the array [1,2,3,4,5] for x,y and z each equal 1.
for x = 1, choose any one element from the array. Them maximum element is 5, so choose that one. It is the maximum profit under this scenario.
for y = 1, choose any subarray of two elements:[1,2],[2,3],[3,4] or [4,5]. The last subarray has the highest sum (profit) of 9.
for z = 1, the maximum profit is obtained with the subarray [3,4,5] with a sum of 12.

if you can choose one of each, maximum profit would be obtained by ignoring x then using y and z to capture [1,2] and [3,4,5] or [1,2,3] and [4,5] for a total profit of 15.

Function Description:
def calculateProfit(arr,x,y,z):
constraints:
1<=n<=200
-10^5 <=arr[i] <= 10^5
0 <=x,y,z <= 20

Sample Input 1
n = 4
arr = [-7, 4, 0, -7]
x = 0
y = 1
z = 0
Sample Output 1
4
Sample Input 2
n = 4
arr = [-6, -3, -3, 10]
x = 0
y = 0
z = 1
Sample Output 2
4
here is my solution but it's not working for all test cases
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int calculateProfit(vector<int>& a, int x, int y, int z){
int n = a.size();
int res = 0;
auto profit = [&](int size){
int curr = 0;
int l = 0;
int r = 0;
while(r < n){
if (r - l < size){
curr += a[r];
r++;
}else {
curr -= a[l];
l++;
}
if (r - l == size){
res = max(res, curr);
}
}
};
for (int i=0; i<x; i++){
profit(1);
}
for (int i=0; i<y; i++){
profit(2);
}
for (int i = 0; i<z; i++){
profit(3);
}
return res;
}

int main(){
vector<int> a1 = {-7, 4, 0, -7};
int x1 = 0;
int y1 = 1;
int z1 = 0;
cout << calculateProfit(a1, x1, y1, z1) << endl;

vector<int> a2 ={-6, -3, -3, 10};
int x2 = 0;
int y2 = 0;
int z2 = 1;
cout << calculateProfit(a2, x2, y2, z2) << endl;

vector<int> a3 = {5,3};
int x3 = 1;
int y3 = 0;
int z3 = 0;
cout << calculateProfit(a3, x3, y3, z3) << endl;
}`Preformatted text`

Based on what i understand, this is the code i have written.

#include<iostream>
using namespace std;

int main()
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int x,y,z;
cin>>x>>y>>z;

for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
if(arr[i]< arr[j])
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
int counter = 0,arrx[1*x],arry[2*y],arrz[3*z];
while(z!=0)
{
for(int i=0;i<3;i++)
{
arrz[i] = arr[counter];
counter += 1;
}
z--;
}
while(y!=0)
{
for(int i=0;i<2;i++)
{
arry[i] = arr[counter];
counter += 1;
}
y--;
}
while(x!=0)
{
for(int i=0;i<1;i++)
{
arrx[i] = arr[counter];
counter += 1;
}
x--;
}
int sumx=0,sumy=0,sumz=0,sizex,sizey,sizez;
sizex = sizeof(arrx)/sizeof(arrx[0]);
sizey = sizeof(arry)/sizeof(arry[0]);
sizez = sizeof(arrz)/sizeof(arrz[0]);
for(int i=0;i<sizex;i++)
{
sumx = sumx + arrx[i];
}
for(int i=0;i<sizey;i++)
{
sumy = sumy + arry[i];
}
for(int i=0;i<sizez;i++)
{
sumz = sumz + arrz[i];
}

cout<<sumx + sumy+ sumz;

}

This clearly is a DP problem

#include<bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using ll = long long;
using ld = long double;
using namespace std;
using namespace __gnu_pbds;

#define int  long long
#define endl "\n";
#define ff first
#define ss second
#define pb push_back
#define FLASH ios_base::sync_with_stdio(false);cin.tie(NULL);
#define MOD 1000000007

// ================================== take ip/op like vector,pairs directly!==================================
template<typename typC,typename typD> istream &operator>>(istream &cin,pair<typC,typD> &a) { return cin>>a.first>>a.second; }
template<typename typC> istream &operator>>(istream &cin,vector<typC> &a) { for (auto &x:a) cin>>x; return cin; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const pair<typC,typD> &a) { return cout<<a.first<<' '<<a.second; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const vector<pair<typC,typD>> &a) { for (auto &x:a) cout<<x<<endl; return cout; }
template<typename typC> ostream &operator<<(ostream &cout,const vector<typC> &a) { int n=a.size(); if (!n) return cout; cout<<a[0]; for (int i=1; i<n; i++) cout<<' '<<a[i]; return cout; }
// ===================================END Of the input module ==========================================
vector<vector<vector<vector<int>>>> memo;

int solution(int i, int x, int y, int z, int n, vector<int>& arr) {
if (i >= n) return 0;
if (memo[i][x][y][z] != -1) {
return memo[i][x][y][z];
}

int a1 = 0;
int a2 = 0;
int a3 = 0;

if (x > 0)
a1 = arr[i] + solution(i + 1, x - 1, y, z, n, arr);

// Size 2
if (i <= n - 2 and y > 0) {
a2 = arr[i] + arr[i + 1] + solution(i + 2, x, y - 1, z, n, arr);
}

// Size 3
if (i <= n - 3 and z > 0) {
a3 = arr[i] + arr[i + 1] + arr[i + 2] + solution(i + 3, x, y, z - 1, n, arr);
}

memo[i][x][y][z] = max({a1, a2, a3});

return memo[i][x][y][z];
}
int calculateProfit(vector<int> arr,int x,int y,int z){
int n=arr.size();
memo.assign(n + 1, vector<vector<vector<int>>>(x + 1, vector<vector<int>>(y + 1, vector<int>(z + 1, -1))));

int ans = solution(0, x, y, z, n, arr);
return ans;
}

void solve() {
int n, x, y, z;
cin >> n >> x >> y >> z;
vector<int> arr(n);
cin >> arr;

int ans=calculateProfit(arr,x,y,z);
cout<<ans<<endl;
}

int32_t main() {
FLASH
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}