candies - interview street problem

candies.cpp

#include <iostream>
using namespace std;
int main() {
  
  
  int N;
  //Get Number of students
  cin>>N;
  
  //initialize rating and candidates array 
  int *rating =  new int[N];
  int *candies = new int[N];
 
 //get rating of each student
  for (int i=0; i<N; i++){
        cin>>rating[i];
  }
  
  for ( int i = 0; i<N ; i++){
  
      //Each student gets at least one candy
      candies[i] = 1 ;
      
     //Check boundary condition
      if( i-1 >= 0){
         
          //Look for previous student rating and if it less than current student
          //assign the current student rating to the previous student rating plus one
          if( rating[i-1] < rating[i]){
              candies[i] = candies[i-1]+1;
          }
          //Other wise if  previous student rating is greater than current student 
          //Imagine it as slope of mountain for example consider rating in decreasing order( 9 8 7 6 5 4)
          // so the number of candies has to increased for all previous students 
          else {
               int j = i;
               
               while (j>0 && rating[j-1] > rating[j])
               {
               //check is the current student already has max number of candidates
               //for example if students are arranged in below fashion
               // 123456 7 5432
               //here 7 will have more candies if we go back from 2 it will result in 5/4 candies which violates the rule from the front
                candies[j-1] = max(candies[j-1],candies[j] + 1);
                j= j-1;
               }          
          }
      }
  }
      //sum up all the candies of the students
    int total = 0;
    for ( int i = 0; i<N ; i++){
        total += candies[i];
    }
    //display the candies
   cout<<total;
  system("pause");
  return 0;
}

nice :), helped me figure out a bug in my code.

In worst case it is O(N^2) solution.

Is there a better solution for this problem ??