debayan
BAN USERkadanes algo ..
keep scanning through the array and calculating the maximum sub-array that ends at every position. The sub-array will either contain a range of numbers if the array has intermixed positive and negative values, or it will contain the least negative value if the array has only negative values.
void maxSumSubArray( int *array, int len, int *start, int *end, int *maxSum )
{
int maxSumSoFar = -2147483648;
int curSum = 0;
int a = b = s = i = 0;
for( i = 0; i < len; i++ ) {
curSum += array[i];
if ( curSum > maxSumSoFar ) {
maxSumSoFar = curSum;
a = s;
b = i;
}
if( curSum < 0 ) {
curSum = 0;
s = i + 1;
}
}
*start = a;
*end = b;
*maxSum = maxSumSoFar;
}
O(n)
- debayan March 16, 2013compute 1 ) sum of 1-n sum = a + b
2 ) sq of sum of 1- n . sum_sq = a^2 + b^2
O(n)
compute sum of input numbers in array
sum1 = a + b
sum_sq1 = a^2 + b ^2
O(n)
sum - sum1 = sum of missing two numbers say (x + y )
sum_sq - sum_sq1 = x^2 + y^2
now : xy = ((x+y) ^ 2 - (a^2 + b^2)) / 2
so , x- y = sq (( x-y)^2) = sq ((x+y)^2) -4xy )
once we get x-y and x+y we can solve and get two number value .
this is the quickest way .
correct me if i am wrong
Repjanicepdaniels1, Backend Developer at Accenture
I decided to become an entrepreneur and work for myself because I wasn't making the money I wanted to ...
Repalicegpopa, Apple Phone Number available 24/7 for our Customers at AMD
I am working as a U.S. marshal in Pro Property Maintenance. I want to write about I Want My ...
you should also make copy constructor and assignment operator as private ... apart from making constructor as private
- debayan May 02, 2013