Write in Java. Program need to have runtimes < n^2 to satisfy the runtime effici
ID: 3914613 • Letter: W
Question
Write in Java. Program need to have runtimes < n^2 to satisfy the runtime efficiency of some of the testsets.
Question 3: June and her Chocolates
June is a kindergarten teacher who wants to give some chocolates to the children of her class. All the children are well behaved and sits in a line. However, each of them has a numeric rating score according to their class performance. June wants to give at least 1 candy to each child.
However, if two children sit next to each other, the one with the higher rating must get more candies. But June wants to minimize the total number of candies she needs to buy. For example, if her students’ ratings are {4, 6, 4, 5, 6, 2}, she can give the following minimal amounts: {1, 2, 1, 2, 3, 1}. She must buy a minimum of 10 candies.
Input:
• The first line contains an integer,n, the size of array A.
• Each of the next n lines contains an integer A[i] indicating the rating of the student at each position i.
Output: The minimum number of candies June needs to buy
Constraints:
1. 1 ? n ? 10^5
2. 1 ? arr[i] ? 10^5
June can give in the following order: {1, 2, 1, 2, 1, 2, 3, 4, 2, 1}
input
10
2
4
2
6
1
7
8
9
2
1
output
19
Explanation / Answer
import java.util.*;
public class choclate {
public static void main(String args[] ){
int n,i,total=0;
Scanner in=new Scanner(System.in);
n=in.nextInt();
int rating[]=new int[n];
int value[]=new int[n];
for(i=0;i<n;i++) {
rating[i]=in.nextInt();
value[i]=1;
}
for(i=0;i<n;i++) {
if(i==0) {
if(rating[i]>rating[i+1])value[i]++;
}
else if(i==n-1) {
if(rating[i]>rating[i-1])value[i]=value[i-1]+1;
}
else {
if(rating[i]>rating[i-1]&&rating[i]>rating[i+1]) {
value[i]=(value[i-1]>value[i+1]?value[i-1]:value[i+1])+1;
}
else if(rating[i]>rating[i-1])value[i]=value[i-1]+1;
else if(rating[i]>rating[i+1])value[i]=value[i+1]+1;
}
total+=value[i];
}
System.out.println(total);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.