What i need help with is making my test cases and adding comments, but here is the information for the code bellow:

(in java) In this project we will consider the Maximum Subarray (or Largest Sum Contiguous Subarray). You have to implement, optimize and analyze three different algorithms that solve the same problem.

Problem Motivation: Suppose you are a freelancer and that you plan to work at a Mykonos resort for some part of the n-day summer season next year. Unfortunately, there isn't enough work for you to be paid every day and you need to cover your own expenses (but you want to go). Fortunately, you know in advance that if you are at the resort on the ith day of the season, you'll make pi euros where pi could be negative (if expenses are more than earnings) or positive (if expenses are less than earnings). To maximize your earning you should choose carefully which day you arrive and which day you leave; the days you work should be consecutive and you don't need to work all season. For example, if n = 8 and p1 = 9 , p2 = 10 , p3 = 8 , p4 = 10 , p5 = 5 , p6 = 4 , p7 = 2 , p8 = 5 then if you worked from day 2 to day 5, you would earn 10 8 + 10 + 5 = 17 euros in total. Assume the resort pays your air tickets.

Facts: When all numbers are positive, then all days are the answer, but when all numbers are negative; no days are selected and the total is 0. Your result should always be 0 or a positive number. Hint: use arrays. The output is the maximum sum, as well as the arriving and departing day.

A. The first algorithm is a brute force O(n²) algorithm that considers all possible pairs of arriving and departing dates. The outer loop picks the beginning element, the inner loop finds the maximum possible sum with the first element picked by the outer loop and compares this maximum with the overall maximum.

B. The second algorithm is a divide and conquer O(n lg n) algorithm. The basic idea follows:Algorithm D&C (pseudocode)

Use a Divide and Conquer approach. The idea follows

1)Divide the given array in two halves

2)Return the maximum of the following three

....a)Maximum subarray sum in left half (Make a recursive call)

....b)Maximum subarray sum in right half (Make a recursive call) ....

.....c)Maximum subarray sum such that the subarray crosses the midpointFor 2c) we can easily find the crossing sum as follows: simply combine the left part and the right part.

Basically, that method finds the maximum sum starting from mid point and ending at some point on left of mid, then finds the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1 and adding them together.

C.The third algorithm is a (dynamic programming) O(n) algorithm, known as Kadane's Algorithm. The basic idea is that you keep only positivecontiguoussummations that we compute by adding one element each time, kept in maxTemp, and at the end keep the best, and save in maxSum. In the next pseudocode, also the arrival and depart index are computed.

Kadane's Algorithm:

//Initialize

maxSum = 0

maxTemp= 0

arrive=-1

depart=-1

tempArrive=0

for i=0 to n-1 in array a

(a) maxTemp = maxTemp + a[i]

(b) if(maxTemp < 0)

maxTemp = 0

arrive=i+1 //next day is the arrival since i-th not included(c) if(maxSum < maxTemp)

maxSum = maxTemp

depart=i

tempArrive=arrive

arrive=tempArrive

return (maxSum, arrive, depart)

returns depart = -1 if sum is <0

[-3, -4, -2]

	maxtemp	maxsum	arrive	depart	temparrive
	-3	0
i=0	0	0	1
i=1
			3

notes on comments:

Your header comment must describe what your program does.

You must include a comment explaining the purpose of every variable or named constant you use in your program.

You must use meaningful identifier names that suggest the meaning or purpose of the constant, variable, function, etc.

Precede every major block of your code with a comment explaining its purpose.

You must use indentation and blank lines to make control structures more readable

Test cases:

1. Consider the tests that are given inmaxSumtest.txt¹use them for the JUnits. The file has one test case per line (10 cases each with 100 entries).

A line corresponding to the examples in the above file would be of the form

[array], sum, arrive, depart

2. You can try other simple examples as these two with an array size of 8

-2-3 4 -1 -2 1 5 -37 2 6

-3 -4 -5 -6 -7 -8 -9 -10 0 0 -1

Additionally, you should test it for various small and different cases.

3. For doing the experimental analysis of the running time, plot the running times as a function of the input size. Run each of your algorithms on random input arrays of size n=100, 200, 500,1000, 2000, 5000, 10000, (for each size/algorithm run 10 times and take average). The first algorithm (a) may be very slow, therefore go up to 1000 only. Remember to have positive and negative numbers.

2

For example,

for i = 1 to 10

create a random array a[] n (size) elements

start clock

run maxSubarrayAlgorithm(a)

stop clock

add to elapsed time

return (elapsed time/10)

Note: Do not include the time to generate the random arrays.

Help withpseudo-random number generation:

//Set seed value as 20, so that every time you get the same sequence of random numbers

Random r=new Random();

r.setSeed(20);

either use nextDouble(): double d = random.nextDouble(); int j = (int)(d*arr.length);

Or nextInt()

Plots for running time

Plot the running times as a function of input size for each algorithm in a single plot. Label your plot (axes, title, etc.) seearticle.

Include an additional plot of the running times on a log-log axis. See here for an explanation:http://en.wikipedia.org/wiki/Log-log_graph. Note that if the slope of a line in a log log plot is m, then the line is of the form O(x^m) on a linear plot. Check this video:http://www.khanacademy.org/math/algebra/logarithms/v/logarithmic-scale

my code:

Iterative Method:

public class Solution {

private static int arrive=-1;

private static int depart=-1;

private static int sum=0;

//Function which find the arrive , depart and largest contiguous sum for given array

private static void findMaxSumIndex(int[] arr){

int maxSumTillNow = Integer.MIN_VALUE;

int tempStartIndex = 0;

int tempSum = 0;

for (int i = 0; i < arr.length; i++) {

tempSum = tempSum + arr[i];

if(tempSum > maxSumTillNow){

maxSumTillNow = tempSum;

arrive = tempStartIndex;

depart = i;

sum = maxSumTillNow;

}

if(tempSum<0){

tempSum = 0;

tempStartIndex = i + 1;

}

}

}

Explanation:

Solution:

Iterative Method:

public class Solution {

private static int arrive=-1;

private static int depart=-1;

private static int sum=0;

//Function which find the arrive , depart and largest contiguous sum for given array

private static void findMaxSumIndex(int[] arr){

int maxSumTillNow = Integer.MIN_VALUE;

int tempStartIndex = 0;

int tempSum = 0;

for (int i = 0; i < arr.length; i++) {

tempSum = tempSum + arr[i];

if(tempSum > maxSumTillNow){

maxSumTillNow = tempSum;

arrive = tempStartIndex;

depart = i;

sum = maxSumTillNow;

}

if(tempSum<0){

tempSum = 0;

tempStartIndex = i + 1;

}

}

}

public static void main(String[] args) {

int[] arr = {-2,-3,4,-1,-2,1,5,-3};

findMaxSumIndex(arr);

System.out.println("Arrive index :"+arrive);

System.out.println("Depart index :"+depart);

System.out.println("Sum :"+sum);

}

}

OUTPUT:

Arrive index :2

Depart index :6

Sum :7

Recursive Method:

public class Solution {

private static int sum=0;

// Find the maximum possible sum in arr[] such that arr[middle] is part of it

static int maxPossibleSum(int arr[], int start, int middle, int end)

{

// Include elements on left of mid.

int sum = 0;

int left_sum = Integer.MIN_VALUE;

for (int i = middle; i >= start; i--)

{

sum = sum + arr[i];

if (sum > left_sum)

left_sum = sum;

}

// Include elements on right of mid

sum = 0;

int right_sum = Integer.MIN_VALUE;

for (int i = middle + 1; i <= end; i++)

{

sum = sum + arr[i];

if (sum > right_sum)

right_sum = sum;

}

// Return sum of elements on left

// and right of mid

return left_sum + right_sum;

}

static int maxContiguousSubArraySum(int arr[], int start, int end)

{

// Base Case: Only one element

if (start == end)

return arr[start];

// Find middle point

int middle = (start + end)/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 */

return Math.max(Math.max(maxContiguousSubArraySum(arr, start, middle),

maxContiguousSubArraySum(arr, middle+1, end)),

maxPossibleSum(arr, start, middle, end));

}

/* Driver program */

public static void main(String[] args)

{

int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};

sum = maxContiguousSubArraySum(arr, 0, arr.length-1);

System.out.println("Sum : "+ sum);

}

}