recategorized by
4,382 views
2 votes
2 votes

Here is the question :

Find out the maximum sub-array of non negative numbers from an array.
The sub-array should be continuous. That is, a sub-array created by choosing the second and fourth element and skipping the third element is invalid.

Maximum sub-array is defined in terms of the sum of the elements in the sub-array. Sub-array A is greater than sub-array B if sum(A) > sum(B).

Example:

A : [1, 2, 5, -7, 2, 3]
The two sub-arrays are [1, 2, 5] [2, 3].
The answer is [1, 2, 5] as its sum is larger than [2, 3]

NOTE: If there is a tie, then compare with segment's length and return segment which has maximum length
NOTE 2: If there is still a tie, then return the segment with minimum starting index

Now , here is the solution I have:

	public ArrayList<Integer> maxset(ArrayList<Integer> a) {
	 
	 long maxSum = 0;
	    long newSum = 0;
	    ArrayList<Integer> maxArray = new ArrayList<Integer>();
	    ArrayList<Integer> newArray = new ArrayList<Integer>();
	    for (Integer i : a) {
	        if (i >= 0) {
	            newSum += i;
	            newArray.add(i);
	        } else {
	            newSum = 0;
	            newArray = new ArrayList<Integer>();
	        }
	        if ((maxSum < newSum) || ((maxSum == newSum) && (newArray.size() > maxArray.size()))) {
	            maxSum = newSum;
	            maxArray = newArray;
	        }
	    }
	    return maxArray;
	    
	}

But , I think the condition of

(newArray.size() > maxArray.size())

is wrong , as it is never getting satisfied. Should it be 

(newArray.size() == maxArray.size())

?

recategorized by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
Pooja Palod asked Oct 9, 2015
483 views
What does find max subarray return when all elements of array are negative?
1 votes
1 votes
1 answer
2
Pooja Palod asked Oct 5, 2015
384 views
number of non negative integer solution for1)x1+x2+x3+x4+x5
0 votes
0 votes
1 answer
4