Candies

                            Solution in C :

In   C :





#include <stdio.h>
#include <stdlib.h>

#define MAXN 100000

struct stu{
    int id;
    int rating;
};

int comp( const void*p1, const void*p2){
    return ((struct stu*)p1)->rating - ((struct stu*)p2)->rating;
}

struct stu student[MAXN];
int candies[MAXN];
int ratings[MAXN];

int main(int argc, char *argv[])
{
    int N;
    int i,j;
    int candy;
    int id;
    long long sumcandies = 0;

    scanf("%d",&N);
    for(i = 0; i < N; i++){
        scanf("%d",&student[i].rating);
        student[i].id = i;
        ratings[i] = student[i].rating;
    }

    qsort(student,N,sizeof(struct stu),comp);
    
    for(i = 0; i < N; i++){
        id = student[i].id;
        candy = 1;

        if(id > 0){
            if(candies[id-1] != 0 && ratings[id] > ratings[id-1]){
                candy = candies[id-1] + 1;
            }
        }

        if(id < N-1){
            if(candies[id+1] != 0 && ratings[id] > ratings[id+1] &&
               candy <= candies[id+1]){
                candy = candies[id+1] + 1;
            }
        }

        sumcandies += candy;
        candies[id] = candy;
    }

    printf("%lld\n",sumcandies);
    return 0;
}
                        

                        Solution in C++ :

In    C++ :




#include <cstdio>
#include <string>
using namespace std;

typedef long long ll;

int a[100005],b[100005];

inline int maxi(int x,int y) {
	return (x>y)?x:y;
}

int main() {
int i,j,n;
ll ans;

	scanf("%d",&n);
	for (i=1;i<=n;++i) {
		scanf("%d",&a[i]);
	}
	a[0]=a[1];
	a[n+1]=a[n];
	for (i=1;i<=n;++i) {
		if ((a[i]<=a[i+1]) && (a[i]<=a[i-1])) {
			b[i]=1;
			for (j=i-1;j && (a[j]>a[j+1]);--j) {
				b[j]=b[j+1]+1;
			}
			for (;i<n && (a[i+1]>a[i]);++i) {
				b[i+1]=b[i]+1;
			}
		}
	}
	ans=0;
	for (i=1;i<=n;++i) {
		if ((a[i]>a[i-1]) && (a[i]>a[i+1])) {
			b[i]=maxi(b[i-1],b[i+1])+1;
		}
		ans+=b[i];
	}
	printf("%Ld\n",ans);
	return 0;

}
                    

                        Solution in Java :

In   Java  :






import java.util.Scanner;
public class Solution{
    
    public static void main(String[] args){
        
Scanner in = new Scanner(System.in);
		
		int N, K;
		N = in.nextInt();
		//K = in.nextInt();
		
		int C[] = new int[N];
		for(int i=0; i<N; i++){
			C[i] = in.nextInt();
		}
        
        int res[] = new int[N];
        for(int i=0 ; i < N ;i++) res[i] =1 ;
        
        int d = N ;
        while(d <= N ){
            
            boolean changed = false; 
        //forward
            for(int i=1 ; i < N ;i++){
                if(C[i-1] < C[i] && res[i-1] >= res[i] ){
                res[i] = res[i-1] +1 ;
                changed = true;
                }
            }
            //backward
         for(int i=N-1 ; i > 0 ;i--){
                if(C[i-1] > C[i] && res[i-1] <= res[i] ){
                res[i-1] = res[i] +1 ;
                changed = true;                
                }
            }
            
            if(!changed)break;
        }
        
 int sum = 0;
        for(int j : res ) sum += j;
        
        System.out.println(sum);
}
}
                    

                        Solution in Python : 
                            
In python3 :






N = int(input())
kids = []
for n in range(N):
    kids.append(int(input()))

def candy(ratings):
    count = 1
    candies = [1]
    for index in range(1, len(ratings)):
        if ratings[index] > ratings[index - 1]:
            count += 1
        else:
            count = 1
        candies.append(count)
        
    return candies

ll = candy(kids)
kids.reverse()
lr = candy(kids)
print(sum(map(max, zip(ll, reversed(lr)))))