Maximum Subarray Sum possible by replacing an Array element by its Square | Java Program to implement the above approach ; Function to find the maximum subarray sum possible ; Stores sum without squaring ; Stores sum squaring ; Stores the maximum subarray sum ; Either extend the subarray or start a new subarray ; Either extend previous squared subarray or start a new subarray by squaring the current element ; Update maximum subarray sum ; Return answer ; Driver Code ; Function call
import java . io . * ; class GFG { public static int getMaxSum ( int a [ ] , int n ) { int dp [ ] [ ] = new int [ n ] [ 2 ] ; dp [ 0 ] [ 0 ] = a [ 0 ] ; dp [ 0 ] [ 1 ] = a [ 0 ] * a [ 0 ] ; int max_sum = Math . max ( dp [ 0 ] [ 0 ] , dp [ 0 ] [ 1 ] ) ; for ( int i = 1 ; i < n ; i ++ ) { dp [ i ] [ 0 ] = Math . max ( a [ i ] , dp [ i - 1 ] [ 0 ] + a [ i ] ) ; dp [ i ] [ 1 ] = Math . max ( dp [ i - 1 ] [ 1 ] + a [ i ] , a [ i ] * a [ i ] ) ; dp [ i ] [ 1 ] = Math . max ( dp [ i ] [ 1 ] , dp [ i - 1 ] [ 0 ] + a [ i ] * a [ i ] ) ; max_sum = Math . max ( max_sum , dp [ i ] [ 1 ] ) ; max_sum = Math . max ( max_sum , dp [ i ] [ 0 ] ) ; } return max_sum ; } public static void main ( String [ ] args ) { int n = 5 ; int a [ ] = { 1 , - 5 , 8 , 12 , - 8 } ; System . out . println ( getMaxSum ( a , n ) ) ; } }