Max subarray hints needed

4
votes

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

I am unable to solve this problem, but I would just like some hints.

It it said this can be solved using Dynamic Programming, but I am struggling to see a connection.

Would the DP connection be taking the sum of the whole array?

2
javaalgorithm
en.m.wikipedia.org/wiki/Maximum_subarray_problem – Tim Biegeleisen
Possible duplicate of Largest sum contiguous subarray (Interview Question) – parsethis
Here's a hint for you. Let's say your array is A[n]. Now build another array B[n] such that B[k] contains the contiguous subarray in A with the biggest sum starting exactly at A[k]. And, as it's typical in DP, build It from the end -- B[n] is obviously just one-element array A[n]. Knowing that, can you determine B[n-1]?... – avysk

2 Answers

-1
votes

A reference for your problem can be found here.

You must use the Kadane's algorithm to solve such a case, which goes something like this:

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
    (a) max_ending_here = max_ending_here + a[i]
    (b) if(max_ending_here < 0)
        max_ending_here = 0
    (c) if(max_so_far < max_ending_here)
        max_so_far = max_ending_here
    return max_so_far

A sample code for your reference:

static int maxSubArraySum(int a[])
{
    int size = a.length;
    int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;

    for (int i = 0; i < size; i++)
    {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}
-1
votes

PLease find Java Code.

public static void findMaxSubArray(int arr[]){

    int max_end_her=arr[0];
    int max_so_far=arr[0];

    int x=arr[0];
    for(int i=1;i<arr.length;i++){
        max_end_her=Math.max(x, max_end_her+arr[i]);
        max_so_far=Math.max(max_so_far, max_end_her);   
    }



System.out.println(max_so_far); 

}