Question: DE Shaw (DESIS Ascend | 17th September 2023) | Subarray Sums | Array Generator
2
Entering edit mode

4
Entering edit mode

Subarray SUM using DP

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n;

int arr[200005];

int dp[200005][5];

int rec(int i, int which)

{

if (i >= n)

{

return 0;

}

if (dp[i][which] != -1)

return dp[i][which];

if (which > 4)

{

return -1e17;

}

int ans = 0;

if (which == 1)

{

int opt1 = arr[i] + rec(i + 1, 1);

int opt2 = rec(i, 2);

ans = max(opt1, opt2);

}

else if (which == 2)

{

int opt1 = -arr[i] + rec(i + 1, 2);

int opt2 = rec(i, 3);

ans = max(opt1, opt2);

}

else if (which == 3)

{

int opt1 = arr[i] + rec(i + 1, 3);

int opt2 = rec(i, 4);

ans = max(opt1, opt2);

}

else

{

int opt1 = -arr[i] + rec(i + 1, 4);

ans = opt1;

}

return dp[i][which] = ans;

}

int32_t main()

{

cin >> n;

for (int i = 0; i < n; i++)

cin >> arr[i];

memset(dp, -1, sizeof(dp));

cout << rec(0, 1);

return 0;

}

3
Entering edit mode

1. Subarray Sum

ll solve(vector<int> &arr){
int n=arr.size();
vector<ll> pf(n),sf(n);
pf[0]=arr[0];
sf[n-1]=arr[n-1];
for(int i=1;i<n;i++) pf[i]=arr[i]+pf[i-1];
for(int i=n-2;i>=0;i--) sf[i]=arr[i]+sf[i+1];
ll sm=0,mn=0;
ll mx=-1e18;
for(int i=0;i<n;i++){
sm+=arr[i];
if(sm>0) sm=0;
mn=min(mn,sm);
mx=max(mx,pf[i]-2*mn-(i<n-1?sf[i+1]:0));
}
return mx;
}

1
Entering edit mode

2) ARRAY GENERATOR

#include <bits/stdc++.h>

using namespace std;

#define int long long

int mod = 1e9 + 7;

int power(int x, int y)

{

int z = 1;

x = x % mod;

while (y > 0)

{

if (y & 1)

z = (z * x) % mod;

y = y >> 1;

x = (x * x) % mod;

}

return z;

}

bool isPrime(int n)

{

for (int i = 2; i * i <= n; ++i)

{

if (n % i == 0)

{

return false;

}

}

return true;

}

signed main()

{

ios::sync_with_stdio(false);

cin.tie(nullptr);

int t;

cin >> t;

while (t--)

{

int n;

cin >> n;

int a[n];

for (int i = 0; i < n; i++)

{

cin >> a[i];

}

sort(a, a + n);

int cnt = 1;

for (int i = 0; i < n; i++)

{

if ((a[i] - i) <= 0)

{

cnt = 0;

break;

}

else

{

int val = a[i] - i;

cnt = ((cnt % mod) * (val % mod)) % mod;

}

}

cout << cnt << "\n";

}

return 0;

}