Candies

Alice is a kindergarten teacher. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her performance in the class.
Alice wants to give at least 1 candy to each child. If two children sit next to each other, then the one with the higher rating must get more candies. Alice wants to minimize the total number of candies she must buy.

Sample Input 1

10
2
4
2
6
1
7
8
9
2
1

Sample Output 1

19

Solution Explanation

we will initialize a new array with value as 1 and size as n to store the candy count. First we go from left to right and if the score of right child is greater than the score of left child then the candy count of right child will be candy count of left child + 1. after this we will start another loop and start from the right and go to left no we will also check if the candy count of left child is less than or equal to the candy count of the right child. If both these conditions are met then we will increase the candy count of the left child to candy count of the right child + 1.

After both loops are completed the count array will have the final count of the candies now we just need to calculate the sum of all the elements of the count array and print it.

Solution in java

import java.util.Arrays;
import java.util.Scanner;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] children = new int[n];
        for (int i = 0; i < n; i++) {
            children[i] = sc.nextInt();
        }
        int[] count = new int[n];
        Arrays.fill(count, 1);
        for (int i = 0; i < n - 1; i++) {
            if (children[i + 1] > children[i]) {
                count[i + 1] = count[i] + 1;
            }
        }
        for (int i = n - 1; i > 0; i--) {
            if (children[i - 1] > children[i] && count[i - 1] <= count[i])
            {
                count[i - 1] = count[i] + 1;
            }
        }
        long result = 0;
        for (int i = 0; i < n; i++) {
            result += count[i];
        }
        System.out.println(result);
        sc.close();
    }
}