You are right the algorithm is based on the max subarray problem. The
difference is the logic to get the crossingSubArray() method. The way it works
is like this:
The outer while loop, makes sure that left position or right position at least
one of this should be between lo and hi values otherw
Here is the code for O (nlgn) time complexity using recursion written in Java:
public class SubArray {
static int A [] = {2, 1, 3, 4, 5};
static int k;
private class Result {
int lo;
int hi;
int total;
I think we can also solve this using divide and conquer:
The algorithm is based on the concept of diving the current array into two
parts and then considering if the solution exists, in the first part from lo to
mid and last part from mid+1 to high and the case in which the subarray crosses
the
@ mohit my first post on here. this solution got ac in spoj
main()
{
unsigned int n,m,sum,max,i,j;
sum=0;max=1;
n=in.ReadNextUInt();
m=in.ReadNextUInt();
unsigned int *a = new unsigned int[n];
unsigned
here it is similar type of question i found on spoj ,it asks only for the
sum
http://www.spoj.pl/problems/HOTELS/
but it is giving TLE in O(n^2)..
On Tue, Nov 29, 2011 at 5:51 PM, Nitin Garg wrote:
> cant think of anything better than O(N^2). Are you sure there exists such
> algo?
>
> On Tue, N
cant think of anything better than O(N^2). Are you sure there exists such
algo?
On Tue, Nov 29, 2011 at 2:55 AM, Mohit kumar lal wrote:
> Given a array of positive integers ,You have to find the largest sum
> possible from consecutive sub-array but sum should be less than or equal to
> K and also
Given a array of positive integers ,You have to find the largest sum
possible from consecutive sub-array but sum should be less than or equal to
K and also find that sub-array. Ex- array={2,1,3,4,5} k=12,
ans->12, sub-array={3,4,5}
Firstly i tried with brute-force and then i also tried to solve i
