Maximum subarray sum in O ( n ) using prefix sum | C ++ program to find out maximum subarray sum in linear time using prefix sum . ; Function to compute maximum subarray sum in linear time . ; Initialize minimum prefix sum to 0. ; Initialize maximum subarray sum so far to - infinity . ; Initialize and compute the prefix sum array . ; loop through the array , keep track of minimum prefix sum so far and maximum subarray sum . ; Driver Program ; Test case 1 ; Test case 2
#include <iostream> NEW_LINE #include <limits> NEW_LINE using namespace std ; int maximumSumSubarray ( int arr [ ] , int n ) { int min_prefix_sum = 0 ; int res = numeric_limits < int > :: min ( ) ; int prefix_sum [ n ] ; prefix_sum [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) prefix_sum [ i ] = prefix_sum [ i - 1 ] + arr [ i ] ; for ( int i = 0 ; i < n ; i ++ ) { res = max ( res , prefix_sum [ i ] - min_prefix_sum ) ; min_prefix_sum = min ( min_prefix_sum , prefix_sum [ i ] ) ; } return res ; } int main ( ) { int arr1 [ ] = { -2 , -3 , 4 , -1 , -2 , 1 , 5 , -3 } ; int n1 = sizeof ( arr1 ) / sizeof ( arr1 [ 0 ] ) ; cout << maximumSumSubarray ( arr1 , n1 ) << endl ; int arr2 [ ] = { 4 , -8 , 9 , -4 , 1 , -8 , -1 , 6 } ; int n2 = sizeof ( arr2 ) / sizeof ( arr2 [ 0 ] ) ; cout << maximumSumSubarray ( arr2 , n2 ) ; return 0 ; }