LCMAX - EDITORIAL

PROBLEM LINK:

Contest

Practice

Setter: Gaurish Baliga

Tester: Rohit Tawde

Editorialist: Gaurish Baliga


DIFFICULTY

Easy-Medium


PREREQUISITES:

Dynamic Programming.


PROBLEM

Abdusatarov was given a task by his discrete mathematics teacher. Being a smart kid, he was able to solve this task very fast and he wants to test if you can do the same.

Given an array, partition it into some arbitrary number of disjoint subarrays such that sum of LCM of all subarrays is maximum.


EXPLANATION

This problem can be solved using Dynamic Programming. We could use a single state i which represents the most optimal answer when we start from index i.

So the transition of our DP would be:

dp_i = \max_{k=i}^{n} (LCM(i...k) + dp_{k+1})


TIME COMPLEXITY:

O(N^2).


SOLUTION

Setter's Solution

    #include<bits/stdc++.h>

    #define int long long

    using namespace std;

    const int MAXN = 2222;

    int a[MAXN], dp[MAXN], n;

    int gcd(int a, int b){return (b == 0 ? a : gcd(b, a%b));}

    int f(int index)

    {

        if(index == n) return 0;

        if(dp[index] != -1) return dp[index];

        int answer = 0, lcm = 1;

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

        {

            lcm /= gcd(a[i], lcm); lcm *= a[i];

            answer = max(answer, lcm + f(i + 1));

        }

        return dp[index] = answer;

    }

    int32_t main()

    {

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

        cin >> n;

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

        {

            cin >> a[i];

        }

        cout << f(0) << "\n";

    }

Tester's Solution

    #include<bits/stdc++.h>

    #define ll long long

    #define pb push_back

    #define F first

    #define S second

    #define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

    using namespace std;

    int main() {

        fast_io;

        int t;

        t=1;

        while(t--){

            ll n;

            cin>>n;

            vector<ll>a(n);

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

                cin>>a[i];

            }

            vector<ll>dp(n,0);

           

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

                ll k =a[i];

                ll ans=a[i];

                for(int j =i-1;j>=0;j--){

                    ans=max(ans,dp[j]+k);

                    ll g1=__gcd(k,a[j]);

                    ll g2=__gcd(k,g1);

                    k/=g2;

                    g1/=g2;

                    ll k1=a[j]/g1;

                    k=(k*k1);

                }

                ans=max(ans,k);

                dp[i]=ans;

            }

           

            cout<<dp[n-1]<<endl;

        }

        return 0;

    }

1 Like