Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time will be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking N/K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin Gar
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking N/K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin G
I don't think it is O(N*K)
It is O(N^2)
Just to confirm if i have understood correctly
Lets say n and k are given and are global to all subproblems
Subproblem Definition
F[i,j] -> maximum expected sum that we can get by partitioning array from 0
to i into j subarrays. Each subarray satisfies the s
Hi
I may not have understood your solution properly. But i think that
your solution is an implementation of brute force where you are
dealing with all cases valid in the range n/2k and 3n/2k without any
optimization with regard to DP. Am i right?
On Nov 28, 2:17 am, sourabh wrote:
> Consider the
O(N*K)
On Nov 28, 1:04 pm, Nitin Garg wrote:
> @Sourabh - whats the running time?
>
>
>
>
>
>
>
>
>
> On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg wrote:
> > Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
>
> > Nice thinking man and thanks :)
>
> > On Mon, Nov 28, 2011
@Sourabh - whats the running time?
On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg wrote:
> Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
>
> Nice thinking man and thanks :)
>
>
>
>
> On Mon, Nov 28, 2011 at 2:47 AM, sourabh wrote:
>
>> Consider the example that you have
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh wrote:
> Consider the example that you have given:
> [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
>
> Now we need to partition the array into 3
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this cons
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh wrote:
> Looks like a dynamic programming problem
>
> Say F(n,k) denotes the maximum expected sum value f
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) <= r <= floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base conditio
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover wrote:
> Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
> Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
> why this is not the optimal split???
>
>
>
>
>
>
>
> On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg wro
13 matches
Mail list logo
