Intervals of Monotonicity( divide array in minimum pats such that each part will be either increasing or decreasing )

Intervals of Monotonicity

statement is very bad mainly in this question we have to find minimum no segment
in which we can partionaise the given function values , each segment will be either
non decreasing or non increasing

It’s well known that a domain of any continuous function may be divided into intervals where the function would increase monotonically or decrease monotonically. A number of intervals of such a partition we will call a complexity of the partition. A complexity of a continuous function is the minimal possible complexity of partition in the domain into the monotonicity intervals.

The notion of complexity may be defined not only for continuous functions. In particular, it is applicable to the functions specified on a grid.

Input

The input contains a description of a function F, specified on a grid. The first line contains two numbers A and B — the first and the last point of the integer grid with step 1 (0 ≤ A < B ≤ 100 000). The second line contains the values table of the function F. The table consists of the integers F(A), F(A+1), …, F(B) separated with a space and/or linefeeds. All the values of the function F are in diapason from –100 000 to 100 000.

Output

Output the only number — the complexity of the function F.

Sample

input	output
1 10 1 2 3 4 2 1 -1 3 6 7	3

Problem Author: Alexander Klepinin
Problem Source: USU Championship 2004

Tags: dynamic programming  (

hide tags for unsolved problems

 )

----------------------------------------EDITORIAL------------------------------------------------------------------

THIS IS A N*2 DP,  IF WE PLAY GREADLY THAN THIS WILL GIVE WA,

CONCEPT-- 

Initilly remove consecutive repetation bcoz it does not make any sence also cause tough to handle,

now start iteratin from the first element , say we reach to it element  now there are 2 option for ith element  whether it is a part of increasing sequence or it is a part of decreasing so consider it as both ,

case1 - suppose we take ith element as a part of increasing sequence that there are 3 options 

// if we are considering i-1th element also as a part of increasing seqeence

   opA- if val[i]>val[i-1] than it can continue with the last increasing segment 

    opB-        if val[i]<val[i-1] than it form a new start of partition and 

/// if we are considering i-1 th elemet as a part of decreasing sequence 

    opC- if we are considering last element as a part of decreasing sequence than there will be a new partition ,

//// similarly if we are considering ith element as a part of decreasing sequence than also there are 3 options .............

--------------------------------------------------code----------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

vector<int> v;

int dp[100000][3];

int main()

 {

  int k,n,z;

   cin>>k>>z;

   n=z-k+1;

   int p=0;

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

    {

     int a;

      cin>>a;

      if(p==0 || v[p-1]!=a) 

{

v.push_back(a);

p++;

}

   }

   int ans=0;

   int size=v.size();

  dp[0][0]=1;// increasing

  dp[0][1]=1;// decreasing

  for(int i=1;i<size;i++)

   {

    // considering ith node as a increasing 

     int temp=INT_MAX;

     // considering from last node also as a increasing

     if(v[i]>v[i-1]) temp=min(temp,dp[i-1][0]);

      else temp=min(temp,dp[i-1][0]+1);

      

      // considering from last node also as a decreasing

      temp=min(temp,dp[i-1][1]+1);

      dp[i][0]=temp; 

      

      //considering ith node as a decreasing

      

        temp=INT_MAX;

    // considering last node as a incresing

         temp=min(temp,dp[i-1][0]+1);

         

         // cosidering last node also as a decreasing

         

         if(v[i]<v[i-1]) temp=min(temp,dp[i-1][1]);

         else temp=min(temp,dp[i-1][1]+1);

         dp[i][1]=temp;

         

   }

   cout<<min(dp[size-1][0],dp[size-1][1])<<endl;

   

   

 }