DE-SHAW interview question help!

general
1

choose k non empty disjoint array from an array of n integers. Let sub_sum[i] denotes the sum of elemtes of ith subarray. the beauty of subarray is
1sub_sum[1] +2 * sub_sum[2]+3 * sub_sum[3]+…+ksub_sum[k]. in other words beauty=summation(i*sub_sum[i]) for 1<+i<=k.
for 1<=i<=k.
given arr and k. find the maximum possible beauty of the array.if it is not possible to choose
k nonempty disjoint subarray return -1;

Note:
A subarray is a contiguous subsegment of an array.
it is not necessary to include every element in a subarray.
The chosen subarray must be disjoint i.e. no two subarrays may contain any common index.
The order of chose subarrays can not be chnaged .if i<j then the last index of ith subarray must be less than the first index of the jth subarray for each possible pair (i,j).

Example 1:
consider n=5, arr =[1,3,-1,-2,1] and k=4
choose the k subarrays as follows (arr[l:r] denotes a subarray inclusive of l and r):
Subarray 1 = arr[1:1]= [1] ; sub_sum[1]=1
Subarray 2 = arr[2:2]= [3] ; sub_sum[1]=3
Subarray 3 = arr[3:3]= [-1]; sub_sum[1]=-1
Subarray 4 = arr[4:4]= [1] ; sub_sum[1]=1
so beauty = 11+23+3*-1+4*1=8
maximum possible answer should return 8;

Example 2:

n=6
arr = [-4,-9,10,1,-3,5]
k=3
output
33

Explanation
choose [-4] [10,1],[5]
sub_sum[1]=-4
sub_sum[1]=11
sub_sum[1]=5
beauty = 1*-4+211+35=33
maximum possible answer should return 33;

2 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int dp[1005][1005][2];

int arr[10005];
int n;
int k;

int rec(int i, int curr, bool is)
{

    if (i >= n)
    {
        if (curr == k)
        {
            return 0;
        }
        else
            return -1e18;
    }
    if (curr > k)
        return -1e17;

    if (dp[i][curr][is] != -1)
        return dp[i][curr][is];

    if (is == 0)
    {
        int opt1 = rec(i + 1, curr, 0);
        int opt2 = (curr)*arr[i] + rec(i + 1, curr, 1);
        int opt3 = curr * arr[i] + rec(i + 1, curr + 1, 0);

        return dp[i][curr][is] = max({opt1, opt2, opt3});
    }

    else
    {

        int opt1 = (curr)*arr[i] + rec(i + 1, curr, 1);
        int opt2 = curr * arr[i] + rec(i + 1, curr + 1, 0);

        return dp[i][curr][is] = max(opt1, opt2);
    }
}

int32_t main()
{

    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    memset(dp, -1, sizeof(dp));

    int cnt = rec(0, 1, 0);

    cout << cnt << endl;
    return 0;
}