Generate an array of maximum sum such that each element exceeds all elements present either on its left or right | Java program for the above approach ; Function to construct the array having maximum sum satisfying the given criteria ; Declaration of the array arrA [ ] and ans [ ] ; Stores the maximum sum of the resultant array ; Initialize the array arrA [ ] ; Traversing the array arrA [ ] ; Initialize the array arrB [ ] ; Assign the maximum element to the current element ; Form the first increasing till every index i ; Make the current element as the maximum element ; Forming decreasing from the index i + 1 to the index N ; Initialize the sum ; Find the total sum ; Check if the total sum is at least the sum found then make ans as ansB ; Print the final array formed ; Driver Code
import java . io . * ; class GFG { static void maximumSumArray ( int arr [ ] , int N ) { int [ ] arrA = new int [ ( N ) ] ; int [ ] ans = new int [ ( N ) ] ; int maxSum = 0 ; for ( int i = 0 ; i < N ; i ++ ) arrA [ i ] = arr [ i ] ; for ( int i = 0 ; i < N ; i ++ ) { int [ ] arrB = new int [ ( N ) ] ; int maximum = arrA [ i ] ; arrB [ i ] = maximum ; for ( int j = i - 1 ; j >= 0 ; j -- ) { arrB [ j ] = Math . min ( maximum , arrA [ j ] ) ; maximum = arrB [ j ] ; } maximum = arrA [ i ] ; for ( int j = i + 1 ; j < N ; j ++ ) { arrB [ j ] = Math . min ( maximum , arrA [ j ] ) ; maximum = arrB [ j ] ; } int sum = 0 ; for ( int j = 0 ; j < N ; j ++ ) sum += arrB [ j ] ; if ( sum > maxSum ) { maxSum = sum ; ans = arrB ; } } for ( int val : ans ) { System . out . print ( val + " ▁ " ) ; } } public static void main ( String [ ] args ) { int A [ ] = { 10 , 6 , 8 } ; int N = A . length ; maximumSumArray ( A , N ) ; } }