Subarray with largest sum - Java
Came across an interesting puzzle and realized that the mind is getting too used to not thinking..need to exercise the brain more often. Anyways, the puzzle is
Given an array containing both positive and negative integers, find the subarray with the largest sum.
BTW, any guesses for the maximum number of subarrays possible for an array of length n? For some reason, took me a long time to figure this out, write to me if you also go through the same, but better still, try to solve it yourself to clear the dust off the mind cells, I am not sure how much I have been able to shake off, but it is worth a try)
Given an array containing both positive and negative integers, find the subarray with the largest sum.
BTW, any guesses for the maximum number of subarrays possible for an array of length n? For some reason, took me a long time to figure this out, write to me if you also go through the same, but better still, try to solve it yourself to clear the dust off the mind cells, I am not sure how much I have been able to shake off, but it is worth a try)
posted by Sonal at 5:11 PM
7 Comments:
By "subarray" I take it you mean a contiguous sequence of elements of the array with length between 0 and the length of the array. Something like
subarray = {array[i],... , array[f-1]},
where
0 <= i <= f <= a.length.
Yes, precisely.
Sounds like an interview question, so here's a bit of a starter. Always go with the brute force solution first, because it's easier to change it into a more clever solution later. I'll use pseudo-python for brevity; transforming this into Java is mostly a mechanical exercise.
(1) do it the brute force O(n^3) way:
for i in range(0, len(array)):
__for j in range(i+1, len(array)):
____if sum(array[i..j] > max):
______max = sum(array[i..j])
______idx = (i,j)
(2) compute S[i] = sum(array[0..i]) in linear time (can be done recursively, or iteratively)
for i in range(0, len(array)):
__for j in range(i+1, len(array)):
____if S[j] - S[i] > max:
______...
That's O(n^2).
(3) For the O(n) solution, that's a bit harder, but consider finding
s = min(S)
t = max(S[i:])
If you can prove that t - s is the sum of the maximum-sum interval, then this problem is solved as efficiently as it can be.
And to answer the next question, yes, these sorts of problems occur all the time in real life, which is why they're actually useful in interviews. The "How much concrete is used annually in Mexico"-type questions, on the other hand, are stupid.
*Kadane's Algorithm(arr[1..n])
begin
(max, a, b) := (-INFINITY, 0, 0)
curr := 0
aa := 1
for bb := 1 to n do
curr := curr + arr[bb]
if curr > max then
(max, a, b) := (curr, aa, bb)
endif
if curr < 0 then
curr := 0
aa := bb + 1
endif
endfor
return (max, a, b)
end
this is the O(n) solution
How about this ?
package careercup;
import java.util.ArrayList;
public class MaximalSubSection {
private final Integer MAX = 5;
private ArrayList < Integer > array = new ArrayList < Integer >(MAX);
private void constructArray(){
for(int i = 0; i < MAX; i++){
array.add(i,i);
}
}
private Integer findMaxSum(){
int sum=0;
for(int i = 0 ; i < array.size(); i++){
sum = max (sum,sum+array.get(i));
}
return sum;
}
private int max(int a, int b) {
// TODO Auto-generated method stub
return ( a > b ? a : b );
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
MaximalSubSection obj = new MaximalSubSection();
obj.constructArray();
int sum = obj.findMaxSum();
System.out.println(sum);
}
}
If we can sort the array then finding the sub array will not be difficult because we would only need to consider positive numbers for the sub-array and ignore the negative. If all the numbers in the array are negative then just pick the least negative number and that would be the sub-array.
public Integer findMaxSum(ArrayList array){
int max_so_far = 0;
int max_ending_here = 0;
for(int i = 0; i < array.size(); i++)
{
max_ending_here = max(0, max_ending_here+array.get(i));
max_so_far = max(max_so_far, max_ending_here);
}
return max_so_far;
}
public int max(int a, int b) {
return ( a > b ? a : b );
}
Post a Comment
<< Home