Question

implement Max Subarray Problem via Divide-and-conquer off this code

#include <iostream>
#define MAX_INT 2147483647
using namespace std;

int main(int argc,char **argv) {

int* array;
int arraySize = 1;

// Get the size of the sequence
cin >> arraySize;
array = new int[arraySize];

// Read the sequence
for(int i=0; i<arraySize; i++){

cin >> array[i];

}

Answer 1

//C++ program

#include <iostream>
#define MAX_INT 2147483647
using namespace std;

int max(int,int);
int CrossingSum(int * , int ,int,int);
int SubArraySum(int* , int,int);

int main(int argc,char **argv) {

int* array;
int arraySize = 1;

// Get the size of the sequence
cin >> arraySize;
array = new int[arraySize];

// Read the sequence
for(int i=0; i<arraySize; i++){

cin >> array[i];

}

cout<<"Maximum subArray sum : "<<SubArraySum(array,0,arraySize-1)<<"\n";
return 0;

}

int max(int a, int b) {
if(a>b)return a;
return b;
}
  
int SubArraySum(int array[], int low, int high)
{
if (low == high)
return array[low];
  
int mid = (low + high)/2;
  
return max(max(SubArraySum(array, low, mid), SubArraySum(array, mid+1, high)), CrossingSum(array, low, mid, high));
}

  
int CrossingSum(int array[], int l, int m, int h)
{
int sum = 0;
int left_half_sum = INT_MIN;
for (int i = m; i >= l; i--)
{
sum = sum + array[i];
if (sum > left_half_sum)
left_half_sum = sum;
}
  
sum = 0;
int right_half_sum = INT_MIN;
for (int i = m+1; i <= h; i++)
{
sum = sum + array[i];
if (sum > right_half_sum)
right_half_sum = sum;
}
  
return left_half_sum + right_half_sum;
}