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

ADD COMMENTlink 9 months ago Delta 2.7k
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;

}

ADD COMMENTlink 9 months ago ------------- • 60
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;
}

ADD COMMENTlink 9 months ago Shristi Chandrakar • 40
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;

}

ADD COMMENTlink 13 days ago Alok Purbey • 10

Login before adding your answer.

APPLY NOWSimilar Posts
Loading Similar Posts