ANSWER IN JAVA

Implement both the Brute Force and Improved versions of the MCS algorithms.

psuedocode for brute force

Input: A sequence a1, a2, a3, ..., an-1, An.

Output: value, start and end of MCS.

Set maxSum < 0

for i= 1 to n do

Set sum <- 0

forj= i to n do

sum <--sum + a,

if (sum > maxSum).

maxSum <- sum

start <-- i

end <--j

Print start, end, maxSum and STOP.

psuedocode for Improved version

Algorithm MCSImproved

Set i <-- 1; Set start<-- end <-- 1

Set maxSum < sum < 0

for j= 1 to n do

sum <-- sum + a;

if (sum > maxSum)

maxSum -- sum

start <-- i

end <-- j

if (sum < 0)

i<-- j+1

sum <-- 0

Print start, end, maxSum and STOP