coderBaba
BAN USER@ all Anonymous and others.
this can be easily done by using the technique called dynamic programming (given that you know about it).
In which we solve smaller problems memorize the result (called memoization ). then combine those solution to get the solution for actual problem. This is applicable for the overlapping problem.
Might be this solution needs some correction to cover all the edge cases.but it works fine in most of the cases.
the idea in itself is good.
@who wrote bullshit soln.
you can't digest new things which you don't know about unless you r willing to learn something new.
if you have; write a better solution than this. it is giving you result in O(n) time.
here is how :
I started with a larger minimum sum (basically infinity ,but 4444 in this case).
compare this with the 1st elem of array. if elem is less that this is new minimum absolute sum.
now, while considering every next element of the array , we have to decide which is the absolute minsum out of abs min sumsofar, current elem, current elem+abs min sum so far.
this can be easily done by memoizing the results of last iteration. if we find new min elem then we start our new abs min sum subarray from this point or if current elem contributes to new abs min sum then we include this in new min sum sub array. or else keep on searching for new abs min.
thus at the end we have the abs min sum for the original array.
in this case we made one decision at every elem of array. and loop runs only once.
this give you O(n) + some const time soln.
your feed backs for any improvement are always welcome.
here is O(n) solution. challenge accepted :)
/*
* File: main.cpp
* Author: vsirohi
*
* Created on September 8, 2012, 9:21 PM
*/
#include <cstdlib>
#include<iostream>
using namespace std;
int mod(int a) // returns a positive integer
{
if(a<0)
a*=(-1);
return a;
}
int min(int a , int b) // returns the integer with min magnitude of two
{ // this do not consider sign (-ve or +ve
int aa= mod(a);
int bb= mod(b);
if(aa<bb)
{ return a; }
else
return b;
}
int ZeroSumSubArry(int array[], int length)
{
int minsum=4444, sumsofar = 4444;
int start =0, end=0;
for(int i=0; i<length; i++) // O[(n)
{
if((mod(array[i]))<(min(sumsofar,sumsofar+array[i])))
{start = i;end = i;}
minsum = min(array[i],minsum+array[i]) ;
if(mod(sumsofar)>mod(minsum))
{
end = i;
}
sumsofar = min(sumsofar, minsum);
}
/// print the sub array. from range start to end.
cout<< " the min sum array is : "<<endl;
for(int k = start; k<=end; k++)
{
cout<<" "<<array[k]<<" ";
}
return sumsofar;
}
int main(int argc, char** argv) {
int arr[7] = {5, -3, -2, 8, 15, -5, 3};
// some random test cases.
//int arr[7] = {5, 3, -2,8,15,-5,3};
//int arr[7] = {1, -1, -2, -1, 2, -1,2};
//int arr[7] = {-1, -2, -3, -1, -2, -2, -1};
// int arr[7] = {0,-1,-2,5, 6,3,1};
int sum=0;
sum = ZeroSumSubArry(arr, 7);
cout << " the sum is : "<<sum<<endl;
return 0;
}
@algos :
for i/p : int arr[3] = {-12, 2, 11};
O/p : the min sum array is :
2 the sum is : 2
RUN SUCCESSFUL (total time: 12ms)
for I/P : int arr[3] = {3, -5, 6};
int sum=0;
sum = greatestsumarraysum(arr, 3);
cout << " the sum is : "<<sum<<endl;
O/P : the min sum array is :
3 -5 the sum is : -2
RUN SUCCESSFUL (total time: 15ms)
for I/P : int arr[7] = {5, 3, -12, 8, 15, -5, 3};
int sum=0;
sum = greatestsumarraysum(arr, 3);
cout << " the sum is : "<<sum<<endl;
O/P : the min sum array is :
3 the sum is : 3
RUN SUCCESSFUL (total time: 11ms)
sorry; But you have to manually change the length of array while calling the fun "greatestsumarraysum" ;
Thanks for pointing.
Please up vote :)
Here Is O(n) solution.
/*
* File: main.cpp
* Author: vsirohi
*
* Created on September 8, 2012, 8:21 PM
*/
#include <cstdlib>
#include<iostream>
using namespace std;
int max(int a , int b)
{
if(a>b)
return a;
else
return b;
}
int greatestsumarraysum(int array[], int length)
{
int maxsum=0, sumsofar = 0;
int start =0, end=0;
for(int i=0; i<length; i++)
{
if(array[i]> maxsum+array[i])
{start = i;end = i;}
maxsum = max(array[i], maxsum+array[i] );
if(sumsofar<maxsum)
{
end = i;
}
sumsofar = max(sumsofar, maxsum);
}
if(sumsofar<0){
cout<<"Error : Invalid Sum "<<endl;
return -1;
}
else{
/// print the sub array. from range start to end.
cout<< " the max sum array is : "<<endl;
for(int k = start; k<=end; k++)
{
cout<<" "<<array[k]<<" ";
}
return sumsofar;
}
}
/*
*
*/
int main(int argc, char** argv) {
int arr[7] = {-5, 3, -2, -2, 6, 3, 4};
int sum=0;
sum = greatestsumarraysum(arr, 7);
cout << " the sum is : "<<sum<<endl;
return 0;
}
here is O(n) solution. challenge accepted :)
/*
* File: main.cpp
* Author: vsirohi
*
* Created on September 8, 2012, 9:21 PM
*/
#include <cstdlib>
#include<iostream>
using namespace std;
int mod(int a) // returns a positive integer
{
if(a<0)
a*=(-1);
return a;
}
int absmin(int a , int b) // returns the integer with absmin magnitude of two
{ // this do not consider sign (-ve or +ve
int aa=a, bb=b;
if(a<0)
aa = mod(a);
if(b<0)
bb= mod(b);
if(aa<bb)
{ return a; }
else
return b;
}
int min(int a, int b)
{
if(a<b)
return a;
return b;
}
int greatestsumarraysum(int array[], int length)
{
int minsum = 4444, sumsofar = 4444, absminsum=4444, absminsumsofar=4444, tempmin = 4444;
int start =0, end=0;
for(int i=0; i<length; i++) // O[(n)
{
absminsum = absmin(array[i], array[i]+absminsum);
minsum = min(array[i], minsum+array[i]);
tempmin = absmin(minsum, absminsum);
tempmin = absmin(tempmin, sumsofar);
absminsumsofar = absmin(tempmin,absminsumsofar);
sumsofar = min(sumsofar, minsum);
}
return absminsumsofar;
}
int main(int argc, char** argv) {
int arr[3] = {-12, 2, 11}; //*/{-5, -3, -2 };//8, 15, -5, 3};
// some random test cases.
// int arr[7] = {5, 3, -12, 8, 15, -5, 3};
//int arr[2] = {5, 3};//, 2};//,8,15,-5,3};
// int arr[7] = {1, -1, -2, -1, 2, -1,2};
//int arr[7] = {-1, -2, -3, -1, -2, -2, -1};
// int arr[7] = {0,-1,-2,5, 6,3,1};
// int arr[5] = {4,5,6, 3,1};
// int arr[3] = {3, -5, 6};
// int arr[7] = {5, 3, -12, 8, 15, -5, 7};
int sum=0;
sum = greatestsumarraysum(arr, 3);
cout << " the sum is : "<<sum<<endl;
return 0;
}
@algos
- coderBaba October 27, 2012thanks for ur feedback buddy.
the bug is fixed :) .
check now.