Jashwanth27's blog

Asked in today OA

By Jashwanth27, history, 7 months ago, In English

A family is about to break their piggy bank to use the money for different purposes. The piggy bank here represents an array (arr[]) consisting of N coins. The family has to split the coins of piggy bank into smaller stack (sub-array) of coins such that the sum of the difference between the maximum value and the minimum value of the coins for all the stacks (sub-arrays) is maximum. Note: Each value of the array can be used only once that is only in one subarray.

5 8 1 7 9 2

Ans = 14 -> (8-1) + (9-2) [8,1] max — 8, min = 1 [7 9 2] max = 9 min = 2

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

which company??

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can sort and do Binary Search. In the check function you can pair up the last element with the first elements and add the difference to a counter and check if you can get counter >=mid

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u code and send it!!

    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you sort, how will you maintain the subarray?

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh seems I read the question so fast that I skipped the word subarray and kept only the word stack in mind

      → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what are the constraints on n? it can be solve with O(n^2) dp

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1<= N <=100 1<= A[i] <= 10^5

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      let dp[j] denotes the max value you can make considering array 0..i 
dp[i] = max(dp[i], dp[j - 1] + (max - min in subarray j..i))
for all j < i
      → Reply
»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

For every subarray the first and last element should be min or max
$$$[a_l,..,a_{min},.,.,a_{max},.a_r]$$$ $$$→$$$ $$$[a_l..a_{min-1}]+[a_{min}..a_{max}]+[a_{max+1}..a_r]$$$ will only increase the answer.
Every subarray should be monotonically increasing or decreasing
$$$[a_{min},..a_i,..a_{max}]$$$ $$$→$$$ $$$[a_{min},..a_{i-1}] + [a_i,..a_{max}]$$$ will increase the answer if $$$a_i < a_{min}$$$

Using these 2 facts you can speedup the bruteforce $$$O(n^2)$$$ dp to $$$O(n)$$$

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Let $$$dp[i]$$$ be the maximum value obtained by partitioning the array upto the $$$i^{th}$$$ index.

At any index $$$i$$$, you can-
$$$1$$$. Start a new partition from $$$i$$$.
$$$2$$$. Include $$$arr[i]$$$ into the previous subarray.

For $$$[1.]$$$, the $$$min$$$ and $$$max$$$ of the new partition would be $$$arr[i]$$$, so $$$dp[i] = dp[i - 1]$$$

For $$$[2.]$$$, we can iterate $$$j$$$ from $$$i$$$ to $$$1$$$ (considering 1-based indexing) and
$$$dp[i] = max(dp[i], max(arr[j], arr[j+1],..., arr[i]) - min(arr[j], arr[j+1], ...arr[i]) + dp[j - 1])$$$

Doable in $$$O(n^2)$$$

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you code and send!

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is the code for recursive DP :-

      int f(int n, vector<int> &dp, vector<int> &a){
    if(dp[n]!=-1){
        return dp[n];
    }
    int val=_inf;
    int maxe=_inf;
    int mine=inf;
    fors(d,0,n-1){
        maxe=max(maxe,a[n-1-d]);
        mine=min(mine,a[n-1-d]);
        int temp=f(n-1-d,dp,a)+maxe-mine;
        val=max(val,temp);
    }
    dp[n]=val;
    return dp[n];
}

void solve()
{
    int n;
    cin>>n;
    vector<int> a(n);
    fors(i,0,n-1){
        cin>>a[i];
    }
    vector<int> dp(n+1,-1);
    dp[0]=0;
    int ans=f(n,dp,a);
    cout<<ans<<endl;
    return;
}

      This code works in $$$O(N^2)$$$ time and $$$O(N)$$$ space.

      → Reply