Minimize the total number of teddies to be distributed | Java implementation of the above approach ; Initializing one tablet for each student ; if left adjacent is having higher marks review and change all the dp values assigned before until assigned dp values are found wrong according to given constrains ; if right adjacent is having higher marks add one in dp of left adjacent and assign to right one ; Driver Code ; n number of students ; marks of students ; solution of problem
public class GFG { static long fun ( int marks [ ] , int n ) { long dp [ ] = new long [ n ] ; int temp ; for ( int i = 0 ; i < n ; i ++ ) dp [ i ] = 1 ; for ( int i = 0 ; i < n - 1 ; i ++ ) { if ( marks [ i ] > marks [ i + 1 ] ) { temp = i ; while ( true ) { if ( ( marks [ temp ] > marks [ temp + 1 ] ) && temp >= 0 ) { if ( dp [ temp ] > dp [ temp + 1 ] ) { temp -= 1 ; continue ; } else { dp [ temp ] = dp [ temp + 1 ] + 1 ; temp -= 1 ; } } else break ; } } else if ( marks [ i ] < marks [ i + 1 ] ) dp [ i + 1 ] = dp [ i ] + 1 ; } int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += dp [ i ] ; return sum ; } public static void main ( String args [ ] ) { int n = 6 ; int marks [ ] = { 1 , 4 , 5 , 2 , 2 , 1 } ; System . out . println ( fun ( marks , n ) ) ; } }