correct1.fl

// This is a correct Divide and Conquer based program for maximum subarray sum problem in fl!
// Algorithm based on https://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/

program MaximumSubarraySum;

// Max array size
@defmacro N 1000

var
	n, max_sum, i : integer;
	arr: array [N] of integer;

// A utility funtion to find maximum of two integers
function max2(a, b:integer): integer;
begin
	if a > b then
		result := a
	else
		result := b;
	return
end;

// A utility funtion to find maximum of three integers
function max(a, b, c:integer): integer;
begin
	result := max2(max2(a,b), c);
	return
end;

// Find the maximum possible sum in arr[] such that arr[m] is part of it
function maxCrossingSum(arr: array [N] of integer; l, m, h: integer): integer;

var
	sum, left_sum, right_sum, i: integer;

begin
	// Include elements on left of mid.
	sum := 0;
	left_sum := -32767; // This is the minimum integer allowed
	for i := m downto l do
	begin
		sum := sum + arr[i];
		if sum > left_sum then
			left_sum := sum
	end;

	 // Include elements on right of mid
	 sum := 0;
	 right_sum := -32767; // This is the minimum integer allowed
	 for i := m+1 to h do
	 begin
		sum := sum + arr[i];
		if sum > right_sum then
			right_sum := sum
	end;
	
	// Return sum of elements on left and right of mid
	result := left_sum + right_sum;
	return
end;

// Returns maximum sum of subarray arr[l..h]
function maxSubArraySum(arr: array [N] of integer; l, h: integer): integer;
var
	m : integer;
	
begin
	// Base Case: Only one element
	if l = h then
	begin
		result := arr[l];
		return
	end;
	
	// Find middle point
	m := (l+h)/2;
	
	(* Return maximum of following three possible cases
     a) Maximum subarray sum in left half
     b) Maximum subarray sum in right half
     c) Maximum subarray sum such that the subarray crosses the midpoint *)
	  
	result := max(maxSubArraySum(arr, l, m), maxSubArraySum(arr, m+1, h), maxCrossingSum(arr, l, m, h));
	return
end;

// Main
begin
	writeString("\nThis is a correct Divide and Conquer based program for maximum subarray sum problem in fl!\n\n");
	writeString("Give me the size of your array: ");
	n := readInteger();
	writeString("\n");
	for i := 0 to n-1 do
	begin
		writeString("Give me value ");
		writeInteger(i+1);
		writeString(": ");
		arr[i] := readInteger()
	end;
	max_sum := maxSubArraySum(arr, 0, n-1);
	writeString("\nMaximum contiguous sum is: ");
	writeInteger(max_sum);
	writeString("\n")
end.