Maximum sum from a subarray by removing atmost 1 element

Maximum sum from a subarray by removing atmost 1 element

  August 31, 2017    

---

Explanation:

Just check with two variables  int max_so_far,cur_max.
create two array 
To get sum from left and right side and by checking whether the subarray till ith position having maximum value from its single element (A[i])or this element + prev sum.

Loop from 1st position to n-2 , check for maximum sum by ignoring sum at index i;

Code:

 public static int maxSumSubarray(int A[], int n)
         {
             int max_so_far=A[0];
int cur_max=A[0];
int fw[]=new int[n];
int bw[]=new int[n];
fw[0]=A[0];
bw[n-1]=A[n-1];
for(int i=1;i<n;++i)
{
cur_max=Math.max(A[i],A[i]+cur_max);
max_so_far=Math.max(max_so_far,cur_max);
fw[i]=cur_max;
}
max_so_far=cur_max=A[n-1];
for(int i=n-2;i>=0;--i)
{
cur_max=Math.max(A[i]+cur_max,A[i]);
max_so_far=Math.max(max_so_far,cur_max);
bw[i]=cur_max;
}
//check if max_so_far is already maximum without any removal
for(int i=1;i<n-1;++i)
{
max_so_far=Math.max(bw[i+1]+fw[i-1],max_so_far);
}
return max_so_far;
         }