Question

Divide-and-Conquer technique is famous for providing O(n log n) solutions for problems with O(n²) straight forward solutions. One of those problems is the “Maximum Subarray Sum” or “Maximum Value Contiguous Subsequence": Given a sequence of n numbers A[0 ... n-1], give an algorithm for finding a contiguous subsequence A[i ... j], for which the sum of elements in this subsequence is the maximum we can get by choosing different i or j.  

For example: the maximum subarray sum for the sequence [-2, 11, -4, 13, -5, 2] is 20. And the maximum subarray sum for [1, -3, 4, -2, -1, 6] is 7.

Of course you can easily design a O(n²) solution of this problem, we don’t want that here though.

Use your newly acquired knowledge of the Divide-and-Conquer algorithm design strategy to design a O(n log n) algorithm for this problem.

Following the classic divide-and-conquer steps noted in lecture 10 will be helpful in your task.

Please also note that we know this problem has a linear time solution using dynamic programming. Do not provide this solution as we will not get the chance to discuss it until next week.

For example:

Test	Input	Result
MaximumSubarraySum(arr);	-2 11 -4 13 -5 2	20
MaximumSubarraySum(arr);	1 -3 4 -2 -1 6	7

Answer 1

Note: As You Haven't Provided any Specific Language and also you have not asked the solution in Divide And Conquer Technique or Dynamic Programming I am going to provide you both the techniques solutions. I have Choosen the Language as Java

Using Dynamic Programming(DP) Solution in Java:

import java.io.*;
import java.util.*;
public class SubArraySum
{
   static int maximumSumSubarray(int arr[], int n)
   {
       int min_prefix_sum = 0;
  
       int res = Integer.MIN_VALUE;
  
       int prefix_sum[] = new int[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 = Math.max(res, prefix_sum[i] -
                       min_prefix_sum);
           min_prefix_sum = Math.min(min_prefix_sum,
                                   prefix_sum[i]);
       }
      
       return res;
   }
   public static void main (String[] args)
   {
       int arr1[] = { -2, 11, -4, 13, -5, 2 };
       int n1 = arr1.length;
       System.out.println(maximumSumSubarray(arr1, n1));
  
  
       int arr2[] = {1, -3, 4, -2, -1, 6 };
       int n2 = arr2.length;
       System.out.println(maximumSumSubarray(arr2, n2));
   }
}

Using Divide And Conquer Technique Solution in Java:

import java.io.*;
import java.util.*;

public class SubArraySum {
   static int maxSum(int arr[], int l,
                               int m, int h)
   {
       int sum = 0;
       int left_sum = Integer.MIN_VALUE;
       for (int i = m; i >= l; i--)
       {
           sum = sum + arr[i];
           if (sum > left_sum)
           left_sum = sum;
       }

       sum = 0;
       int right_sum = Integer.MIN_VALUE;
       for (int i = m + 1; i <= h; i++)
       {
           sum = sum + arr[i];
           if (sum > right_sum)
           right_sum = sum;
       }

       return Math.max(left_sum + right_sum, Math.max(left_sum, right_sum));
   }
   static int maxSubArraySum(int arr[], int l,
                                   int h)
   {
   if (l == h)
       return arr[l];
   int m = (l + h)/2;

   return Math.max(Math.max(maxSubArraySum(arr, l, m), maxSubArraySum(arr, m+1, h)), maxSum(arr, l, m, h));
   }

   public static void main(String[] args)
   {
   int arr[] = {-2, 11, -4, 13, -5, 2};
   int n = arr.length;
   int max_sum = maxSubArraySum(arr, 0, n-1);
   System.out.println(max_sum);
  
   int arr2[] = {1, -3, 4, -2, -1, 6 };
   int n2 = arr2.length;
   System.out.println(maxSubArraySum(arr2,0, n2-1));
   }
}