Friday, February 14, 2020

Minimum number

#include<bits/stdc++.h>
using namespace std;

int findSolution(vector<int> &ratings)
{
    int size = ratings.size();
    if(size==0)
        return 0;

    vector<int> leftToRight(size);
    vector<int> rightToLeft(size);
    int sum;

    leftToRight[0] = 1;
    for(int i=1;i<size;i++)
    {
        if(ratings[i]>ratings[i-1])
            leftToRight[i] = leftToRight[i-1]+1;

        else
            leftToRight[i] = 1;
    }

    sum=leftToRight[size-1];
    rightToLeft[size-1] = 1;

    for(int i=size-2;i>=0;i--)
    {
        if(ratings[i]>ratings[i+1])
            rightToLeft[i] = rightToLeft[i+1]+1;

        else
            rightToLeft[i] = 1;

        sum+=(leftToRight[i]>rightToLeft[i]?leftToRight[i]:rightToLeft[i]);
    }

    return sum;
}

int main()
{
    int n,i;
    cout<<"";
    cin>>n;

    vector<int> a(n);
    cout<<""<<endl;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }

    cout<<""<<endl;
    cout<<findSolution(a)<<endl;

    return 0;
}

No comments:

Post a Comment