Join Us
Loading Similar Posts
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;
}
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;
}
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;
}
