maximum subarray whose sum equals 0
An array contains both positive and negative elements, find the maximum subarray whose sum equals 0. 开发者_StackOverflow中文版
The link in the current accepted answer requires to sign up for a membership and I do not its content.
This algorithm will find all subarrays with sum 0 and it can be easily modified to find the minimal one or to keep track of the start and end indexes. This algorithm is O(n).
Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element(prefix sum of array).
Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j < k, then the sum of the input till j is equal to the sum till k and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k.
- NOTE: if
j + 1 == k, thenk is 0and that's it! ;) - NOTE: The algorithm should consider a virtual
tmp[-1] = 0; - NOTE: An empty array has sum 0 and it's minimal and this special case should be brought up as well in an interview. Then the interviewer will say that doesn't count but that's another problem! ;)
The implementation can be done in different ways including using a HashMap with pairs but be careful with the special case in the NOTE section above.
Example:
int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2}
int[] tmp = {4, 10, 13, 4, -1, 0, 3, 3, 5}
- Value 4 in tmp at index 0 and 3 ==> sum tmp 1 to 3 = 0, length (3 - 1) + 1 = 3
- Value 0 in tmp at index 5 ==> sum tmp 0 to 5 = 0, length (5 - 0) + 1 = 6
- Value 3 in tmp at index 6 and 7 ==> sum tmp 7 to 7 = 0, length (7 - 7) + 1 = 1
****UPDATE****
Assuming that in our tmp array we end up with multiple element with the same value then you have to consider every identical pair in it! Example (keep in mind the virtual '0' at index '-1'):
int[] array = {0, 1, -1, 0}
int[] tmp = {0, 1, 0, 0}
By applying the same algorithm described above the 0-sum subarrays are delimited by the following indexes (included):
[0] [0-2] [0-3] [1-2] [1-3] [3]
Although the presence of multiple entries with the same value might impact the complexity of the algorithm depending on the implementation, I believe that by using an inverted index on tmp (mapping a value to the indexes where it appears) we can keep the running time at O(n).
This is one the same lines as suggested by Gevorg but I have used a hash map for quick lookup. O(n) complexity used extra space though.
private static void subArraySumsZero()
{
int [] seed = new int[] {1,2,3,4,-9,6,7,-8,1,9};
int currSum = 0;
HashMap<Integer, Integer> sumMap = new HashMap<Integer, Integer>();
for(int i = 0 ; i < seed.length ; i ++)
{
currSum += seed[i];
if(currSum == 0)
{
System.out.println("subset : { 0 - " + i + " }");
}
else if(sumMap.get(currSum) != null)
{
System.out.println("subset : { "
+ (sumMap.get(currSum) + 1)
+ " - " + i + " }");
sumMap.put(currSum, i);
}
else
sumMap.put(currSum, i);
}
System.out.println("HASH MAP HAS: " + sumMap);
}
The output generated has index of elements (zero based):
subset : { 1 - 4 }
subset : { 3 - 7 }
subset : { 6 - 8 }
1. Given A[i]
A[i] | 2 | 1 | -1 | 0 | 2 | -1 | -1
-------+---|----|--------|---|----|---
sum[i] | 2 | 3 | 2 | 2 | 4 | 3 | 2
2. sum[i] = A[0] + A[1] + ...+ A[i]
3. build a map<Integer, Set>
4. loop through array sum, and lookup map to get the set and generate set, and push <sum[i], i> into map.
Complexity O(n)
Here's my implementation, it's the obvious approach so it's probably sub-optimized, but at least its clear. Please correct me if i'm wrong.
Starts from each index of the array and calculates and compares the individual sums (tempsum) with the desired sum (in this case, sum = 0). Since the integers are signed, we must calculate every possible combination.
If you don't need the full list of sub-arrays, you can always put conditions in the inner loop to break out of it. (Say you just want to know if such a sub-array exists, just return true when tempsum = sum).
public static string[] SubArraySumList(int[] array, int sum)
{
int tempsum;
List<string> list = new List<string>();
for (int i = 0; i < array.Length; i++)
{
tempsum = 0;
for (int j = i; j < array.Length; j++)
{
tempsum += array[j];
if (tempsum == sum)
{
list.Add(String.Format("[{0}-{1}]", i, j));
}
}
}
return list.ToArray();
}
Calling the function:
int[] array = SubArraySumList(new int { 0, -1, 1, 0 }, 0));
Printing the contents of the output array:
[0-0], [0-2], [0-3], [1-2], [1-3], [3-3]
Following solution finds max length subarray with a given sum k without using dynamic programming, but using simple rescursion. Here i_s is start index and i_e is end index for the current value of sum
##Input the array and sum to be found(0 in your case)
a = map(int,raw_input().split())
k = int(raw_input())
##initialize total sum=0
totalsum=0
##Recursive function to find max len 0
def findMaxLen(sumL,i_s,i_e):
if i_s<len(a)-1 and i_e>0:
if sumL==k:
print i_s, i_e
return (i_s,i_e)
else:
x = findMaxLen(sumL-a[i_s],i_s+1,i_e)
y = findMaxLen(sumL-a[i_e],i_s,i_e-1)
if x[1]-x[0]>y[1]-y[0]:
return x
else:
return y
else:
##Result not there
return (-1,-1)
## find total sum
for i in range(len(a)):
totalsum += a[i]
##if totalsum==0, max array is array itself
if totalsum == k:
print "seq found at",0,len(a)-1
##else use recursion
else:
print findMaxLen(totalsum,0,len(a)-1)
Time complexity is O(n) and space complexity is O(n) due to recursive memory stack
Here's an O(n) implementation in java
The idea is to iterate through the given array and for every element arr[i], calculate sum of elements form 0 to i, store each sum in HashMap.
If an element is
0, it's considerd as a a ZeroSum sub array.if
sumbecame0, then there is a ZeroSum sub array, from0toi.If the current sum has been seen before in
HashMap, then there is a ZeroSum sub array, from that point toi.
Code:
import java.util.*;
import java.lang.*;
class Rextester
{
private static final int[] EMPTY = {};
// Returns int[] if arr[] has a subarray with sero sum
static int[] findZeroSumSubarray(int arr[])
{
if (arr.length == 0) return EMPTY;
// Creates an empty hashMap hM
HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
// Initialize sum of elements
int sum = 0;
for (int i = 0; i < arr.length; i++)
{
sum += arr[i];
if (arr[i] == 0) //Current element is 0
{
return new int[]{0};
}
else if (sum == 0) // sum of elements from 0 to i is 0
{
return Arrays.copyOfRange(arr, 0, i+1);
}
else if (hM.get(sum) != null) // sum is already present in hash map
{
return Arrays.copyOfRange(arr, hM.get(sum)+1, i+1);
}
else
{
// Add sum to hash map
hM.put(sum, i);
}
}
// We reach here only when there is no subarray with 0 sum
return null;
}
public static void main(String arg[])
{
//int arr[] = {};
int arr[] = { 2, -3, 1, 4, 6}; //Case left
//int arr[] = { 0, 2, -3, 1, 4, 6}; //Case 0
//int arr[] = { 4, 2, -3, 1, 4}; // Case middle
int result[] = findZeroSumSubarray(arr);
if (result == EMPTY){
System.out.println("An empty array is ZeroSum, LOL");
}
else if ( result != null){
System.out.println("Found a subarray with 0 sum :" );
for (int i: result) System.out.println(i);
}
else
System.out.println("No Subarray with 0 sum");
}
}
Please see the experiment here: http://rextester.com/PAKT41271
An array contains positive and negative numbers. Find the sub-array that has the maximum sum
public static int findMaxSubArray(int[] array)
{
int max=0,cumulativeSum=0,i=0,start=0,end=0,savepoint=0;
while(i<array.length)
{
if(cumulativeSum+array[i]<0)
{
cumulativeSum=0;
savepoint=start;
start=i+1;
}
else
cumulativeSum=cumulativeSum+array[i];
if(cumulativeSum>max)
{
max=cumulativeSum;
savepoint=start;
end=i;
}
i++;
}
System.out.println("Max : "+max+" Start indices : "+savepoint+" end indices : "+end);
return max;
}
Below codes can find out every possible sub-array that has a sum being a given number, and (of course) it can find out the shortest and longest sub-array of that kind.
public static void findGivenSumSubarray(int arr[], int givenSum) {
int sum = 0;
int sStart = 0, sEnd = Integer.MAX_VALUE - 1; // Start & end position of the shortest sub-array
int lStart = Integer.MAX_VALUE - 1, lEnd = 0; // Start & end position of the longest sub-array
HashMap<Integer, ArrayList<Integer>> sums = new HashMap<>();
ArrayList<Integer> indices = new ArrayList<>();
indices.add(-1);
sums.put(0, indices);
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
indices = sums.get(sum - givenSum);
if(indices != null) {
for(int index : indices) {
System.out.println("From #" + (index + 1) + " to #" + i);
}
if(i - indices.get(indices.size() - 1) < (sEnd - sStart + 1)) {
sStart = indices.get(indices.size() - 1) + 1;
sEnd = i;
}
if(i - indices.get(0) > (lEnd - lStart + 1)) {
lStart = indices.get(0) + 1;
lEnd = i;
}
}
indices = sums.get(sum);
if(indices == null) {
indices = new ArrayList<>();
}
indices.add(i);
sums.put(sum, indices);
}
System.out.println("Shortest sub-arry: Length = " + (sEnd - sStart + 1) + ", [" + sStart + " - " + sEnd + "]");
System.out.println("Longest sub-arry: Length = " + (lEnd - lStart + 1) + ", [" + lStart + " - " + lEnd + "]");
}
Hope this help you.
private static void subArrayZeroSum(int array[] , int findSum){
Map<Integer,HashSet<Integer>> map = new HashMap<Integer,HashSet<Integer>>();
int sum = 0;
for(int index = 0 ; index < array.length ; index ++){
sum +=array[index];
if(array[index] == findSum){
System.out.println(" ["+index+"]");
}
if(sum == findSum && index > 0){
System.out.println(" [ 0 , "+index+" ]");
}
if(map.containsKey(sum)){
HashSet<Integer> set = map.get(sum);
if(set == null)
set = new HashSet<Integer>();
set.add(index);
map.put(sum, set);
for(int val : set){
if(val + 1 != index && (val + 1) < index){
System.out.println("["+(val + 1) +","+index+" ]");
}
}
}else{
HashSet<Integer> set = map.get(sum);
if(set == null)
set = new HashSet<Integer>();
set.add(index);
map.put(sum, set);
}
}
}
One of the solution:
Let's say we have an array of integer, int[] arr = {2,1,-1,-2};
We will traverse using the for loop until we find the number < 0 OR <= 0 i = 2;
With the inner loop, we will traverse assign the value to j = i-1 So, We can able to find the positive value.
for(int i = 0; i<arr.length; i++){
int j = 0;
int sum = arr[i];
if(arr[i] < 0){
j = i - 1;
}
We will have one sum variable, which maintaining the sum of arr[i] and arr[j] and updating the result.
If the sum is < 0 then, we have to move left side of the array and so, we will decrement the j by one, j--
for(j = i-1; j>=0; j--) {
sum = sum + arr[j];
if(sum == 0){
System.out.println("Index from j=" + j+ " to i=" + i);
return true;
}
}
If the sum is > 0 then, we have to move right side of the array and so, we will increment the i
When we find the sum == 0 then we can print the j and i index and return or break the loop.
And so, It's complete in a linear time. As well we don't need to use any other data structure as well.
Another solution to this problem could be: 1. Calculate sum for entire array 2. Now follow following formula to get the largest subarray with sum zero:
Math.max(find(a,l+1,r,sum-a[l]), find(a,l,r-1,sum-a[r]));
where l=left index, r= right index, initially their value=0 and a.length-1
Idea is simple, max size we can get with sum=0, is the size of array then we start skipping elements from left and right recursively, the moment we get sum=0 we stop. Below is the code for same:
static int find(int a[]) {
int sum =0;
for (int i = 0; i < a.length; i++) {
sum = sum+a[i];
}
return find(a, 0, a.length-1, sum);
}
static int find(int a[], int l, int r, int sum) {
if(l==r && sum>0) {
return 0;
}
if(sum==0) {
return r-l+1;
}
return Math.max(find(a,l+1,r,sum-a[l]), find(a,l,r-1,sum-a[r]));
}
Hope this will help.
int v[DIM] = {2, -3, 1, 2, 3, 1, 4, -6, 7, -5, -1};
int i,j,sum=0,counter=0;
for (i=0; i<DIM; i++) {
sum = v[i];
counter=0;
for (j=i+1; j<DIM;j++) {
sum += v[j];
counter++;
if (sum == 0) {
printf("Sub-array starting from index %d, length %d.\n",(j-counter),counter +1);
}
}
}
加载中,请稍侯......
精彩评论