fork download 
  1. // Online C++ compiler to run C++ program online
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. bool check(vector<int>&arr,int j,int i)
  5. {
  6.     int mxEle = -1;
  7.     for(int k=j;k<=i;k++)
  8.         mxEle = max(mxEle,arr[k]);
  9.     if(arr[i]!=mxEle)
  10.         return true;
  11.     else
  12.         return false;
  13. }
  14. vector<int> findLeft(vector<int>&arr,int n)
  15. {
  16.     vector<int> left(n,-1);
  17.     stack<int>s;
  18.     left[0]=-1;
  19.     for(int i=1;i<n;i++)
  20.     {
  21.         while(!s.empty() && arr[s.top()]<=arr[i])
  22.             s.pop();
  23.         if(s.empty())
  24.             left[i] = -1;
  25.         else
  26.         left[i] = s.top();
  27.         s.push(i);
  28.     }
  29.     return left;
  30. }
  31. int solve(vector<int>&arr,int n)
  32. {
  33.     int ans=0;
  34.     vector<int> dp(n,0);
  35.     dp[0]=0;//as single element won;t constitute any shipments
  36.     vector<int>left = findLeft(arr,n);
  37.     vector<int> pref(n,0);
  38.  
  39.     for(int i=1;i<n;i++)
  40.     {
  41.         // for(int j=i-1;j>=0;j--)
  42.         // {
  43.         //     if(check(arr,j,i))
  44.         //     {
  45.         //         if(j==0)
  46.         //             dp[i] = max(dp[i],1);//whole 0 to i single shipment
  47.         //         else
  48.         //             dp[i] = max(dp[i],dp[j-1]+1);
  49.         //     }
  50.         // }
  51.         // ans = max(ans,dp[i]);
  52.         int j = left[i];
  53.         if(j==-1)//no one on left greater then himself
  54.             dp[i]=0;
  55.         else if(j==0)//whole 0 to i be part of single shipment
  56.             dp[i] = max(dp[i],1);
  57.         else if(j+1==i)//edge case say 0,1,4,6,5 a valid and last 2 but 2 itself is not valid so here 5,2 and would combine it and from 6 (i.e j-1)
  58.             dp[i] = max(dp[i],pref[j-1]+1);
  59.         else
  60.         {
  61.             dp[i] = max(dp[i],pref[j]+1);
  62.         }
  63.         cout<<pref[i-1]<<" "<<pref[i]<<" "<<pref[j]<<" "<<dp[i]<<endl;
  64.         pref[i] = max(pref[i-1],dp[i]);
  65.         ans = max(ans,dp[i]);
  66.     }
  67.     return ans;
  68. }
  69. int main() {
  70.     int n;
  71.     vector<int> arr={0, 1, 4, 6, 5, 2};
  72.     n = arr.size();
  73.  
  74.     cout<<solve(arr,n);
  75.     return 0;
  76. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
Standard input is empty
stdout 
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1
1 0 1 1
1
https://ideone.com/eSYe7X
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!