Maximum sum subarray after altering the array | C ++ implementation of the approach ; Function that returns true if all the array element are <= 0 ; If any element is non - negative ; Function to return the vector representing the right to left Kadane array as described in the approach ; Function to return the prefix_sum vector ; Function to return the maximum sum subarray ; Function to get the maximum sum subarray in the modified array ; kadane_r_to_l [ i ] will store the maximum subarray sum for thre subarray arr [ i ... N - 1 ] ; Get the prefix sum array ; To get max_prefix_sum_at_any_index ; Summation of both gives the maximum subarray sum after applying the operation ; Function to return the maximum subarray sum after performing the given operation at most once ; If all element are negative then return the maximum element ; Maximum subarray sum without performing any operation ; Maximum subarray sum after performing the operations of first type ; Reversing the array to use the same existing function for operations of the second type ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool areAllNegative ( vector < int > arr ) { for ( int i = 0 ; i < arr . size ( ) ; i ++ ) { if ( arr [ i ] > 0 ) return false ; } return true ; } vector < int > getRightToLeftKadane ( vector < int > arr ) { int max_so_far = 0 , max_ending_here = 0 ; int size = arr . size ( ) ; for ( int i = size - 1 ; i >= 0 ; i -- ) { max_ending_here = max_ending_here + arr [ i ] ; if ( max_ending_here < 0 ) max_ending_here = 0 ; else if ( max_so_far < max_ending_here ) max_so_far = max_ending_here ; arr [ i ] = max_so_far ; } return arr ; } vector < int > getPrefixSum ( vector < int > arr ) { for ( int i = 1 ; i < arr . size ( ) ; i ++ ) arr [ i ] = arr [ i - 1 ] + arr [ i ] ; return arr ; } int maxSumSubArr ( vector < int > a ) { int max_so_far = 0 , max_ending_here = 0 ; for ( int i = 0 ; i < a . size ( ) ; i ++ ) { max_ending_here = max_ending_here + a [ i ] ; if ( max_ending_here < 0 ) max_ending_here = 0 ; else if ( max_so_far < max_ending_here ) max_so_far = max_ending_here ; } return max_so_far ; } int maxSumSubWithOp ( vector < int > arr ) { vector < int > kadane_r_to_l = getRightToLeftKadane ( arr ) ; vector < int > prefixSum = getPrefixSum ( arr ) ; int size = arr . size ( ) ; for ( int i = 1 ; i < size ; i ++ ) { prefixSum [ i ] = max ( prefixSum [ i - 1 ] , prefixSum [ i ] ) ; } int max_subarray_sum = 0 ; for ( int i = 0 ; i < size - 1 ; i ++ ) { max_subarray_sum = max ( max_subarray_sum , prefixSum [ i ] + kadane_r_to_l [ i + 1 ] ) ; } return max_subarray_sum ; } int maxSum ( vector < int > arr , int size ) { if ( areAllNegative ( arr ) ) { return ( * max_element ( arr . begin ( ) , arr . end ( ) ) ) ; } int resSum = maxSumSubArr ( arr ) ; resSum = max ( resSum , maxSumSubWithOp ( arr ) ) ; reverse ( arr . begin ( ) , arr . end ( ) ) ; resSum = max ( resSum , maxSumSubWithOp ( arr ) ) ; return resSum ; } int main ( ) { vector < int > arr { -9 , 21 , 24 , 24 , -51 , -6 , 17 , -42 , -39 , 33 } ; int size = arr . size ( ) ; cout << maxSum ( arr , size ) ; return 0 ; }