Help me to solve my coding interview question

general
, , ,
1

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
2 
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`
3

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;
	
	
}
4

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;
}