ANSWER IN JAVA

Source code =

public class q1 {

public static void main(String[] args) {

int[] a = { 3, 9, 7, 9, 0, 5, 6 };

int n = a.length;

int maxSum = 0;

int start = 0;

int end = 0;

for (int i = 1; i <= n; i++) {

int sum = 0;

for (int j = i; j < n; j++) {

sum = sum + a[j];

if (sum > maxSum) {

maxSum = sum;

start = i;

end = j;

}

}

}

System.out.println("start : " + start + " end : " + end + " maxSum : " + maxSum);

}

}

Verification/Debugging: Check the correctness of the algorithms for the following sequences. Include the output of your tests in your submissions.

a. -1, -2, -3, -4, -5, -6

b. -1, 1, -1, 1, -1, 1

c. -1, 2, 3, -3, 2

d. 1, -5, 2, -1, 3 MCS: 2, -1, 3

e. -2, 2, -2, -2, 3, 2 MCS: 3, 2