收件人: algogeeks@googlegroups.com
主题: [algogeeks] Re: NxN matrix
Hi, as I understood the question goes like this (I also face this
problem
earlier)...
Given an array of 0s and 1s (whether the array can contain any other
element apart from 0 and 1 is not mentioned in the question
;jm;++j)
if(array[i][j]==-1)
array[i][j]=0;
Best Regards,
James Fang
_
发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] 代表
chandra kumar
发送时间: 2007年11月23日 21:58
收件人: algogeeks@googlegroups.com
主题: [algogeeks] Re: NxN matrix
Hi, as I understood the question
;
Best Regards,
James Fang
_
发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] 代表
chandra kumar
发送时间: 2007年11月23日 21:58
收件人: algogeeks@googlegroups.com
主题: [algogeeks] Re: NxN matrix
Hi, as I understood the question goes like this (I also face this problem
earlier
发送时间: 2007年11月23日 21:58
收件人: algogeeks@googlegroups.com
主题: [algogeeks] Re: NxN matrix
Hi, as I understood the question goes like this (I also face this problem
earlier)...
Given an array of 0s and 1s (whether the array can contain any other
element apart from 0 and 1 is not mentioned
PROTECTED] *代表
*chandra kumar
*发送时间:* 2007年11月23日 21:58
*收件人:* algogeeks@googlegroups.com
*主题:* [algogeeks] Re: NxN matrix
Hi, as I understood the question goes like this (I also face this problem
earlier)...
* Given an array of 0s and 1s (whether the array can contain any other
I have some questions in case 2 questions inlined..
Thanks and regards,
K.V.Chandra kumar.
On 22/11/2007, Dave [EMAIL PROTECTED] wrote:
Case 1
Start:
0 1 1
1 1 1
1 1 1
After first scan:
0 1 0
1 1 1
0 1 1
After second scan:
0 1 0
0 1 1
0 1 1
After third scan:
0 0 0
0 1 1
Hi, as I understood the question goes like this (I also face this problem
earlier)...
* Given an array of 0s and 1s (whether the array can contain any other
element apart from 0 and 1 is not mentioned in the question posted, but to
make it hard people say that the array cannot hold element
I was pretty careless with cut and paste from Case 1. Let's try Case 2
again
Start:
1 1 0
1 1 1
0 1 1
After first scan:
1 1 0
1 1 1
0 1 0
After second scan:
0 1 0
0 1 1
0 1 0
After third scan:
0 0 0
0 1 1
0 1 0
It looks like I need a 4th step. If the lower right element is zero,
zero the last
Then the case
1 1 1
1 1 1
0 1 1
Scan I
1 1 1
1 1 1
0 1 0
Scan II
0 1 1
0 1 1
0 1 0
Scan III
0 1 1
0 1 1
0 0 0 this will the right answer, but cosidering next case, we get
Scan IV
0 1 0
0 1 0
0 0 0
HI Chandra,
As per the problem statement
Given an array of 0's and 1's whenever you encounter an 0 make
corresponding column and row elements 0.
Does it mean make all the rows and column zero or only last row and
column elemnt zero??
could you reframe the problem statement with more details
Hi Dave,
Can you explain your algo for these 2 cases...
0 1 11 1 0
1 1 11 1 1
1 1 10 1 1
Please explain me in steps cause we tried the same problem and can't get
it done for without using extra space. ( we used 1 extra space, if the
Case 1
Start:
0 1 1
1 1 1
1 1 1
After first scan:
0 1 0
1 1 1
0 1 1
After second scan:
0 1 0
0 1 1
0 1 1
After third scan:
0 0 0
0 1 1
0 1 1
Case 2
Start:
1 1 0
1 1 1
0 1 1
After first scan:
0 1 0
1 1 1
0 1 0
After second scan:
0 0 0
0 1 1
0 0 0
After third scan:
0 0 0
0 1 0
0 0 0
Hope
Scan the array. If the i,j element is zero, set the last element of
row i and the last element of column j to zero. Then, scan the last
row, ignoring the last element, and zero every column that ends with a
zero. Similarly, scan the last column, ignoring the last element, and
zero every row that
The explanation above is correct ... O(n^3) is enough.
If you're able to solve the one dimensional array in O(n), then you can
solve the 2D case in O(n^3).
For each row-range [a..b], we'll compute the maximum contiguous subarray
with the O(n) above. To achieve O(n^3), this means that for each
I doubt It will be O(n^3)..
Dynamic programming algorithm, by size of submatrix, will give at
least O(N ^ 4), won't it?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
Does anyone knew more effective solution then DP?
On Oct 12, 3:46 pm, Andrey [EMAIL PROTECTED] wrote:
I doubt It will be O(n^3)..
Dynamic programming algorithm, by size of submatrix, will give at
least O(N ^ 4), won't it?
--~--~-~--~~~---~--~~
You received
I've found task 108 [ http://acm.uva.es/p/v1/108.html ] but there is
nothing except task statement.
I have written a program that solves this problem (see listing below)
but It has complexity = O(N^4).
Please look at my program it's quite simple to understand and prints
debug output
(see at the
int Max1 (int a[], int n)
{
int s = 0;
int r = 0;
int i = 0;
s = a[0];
r = a[0];
for (i = 1; i n; ++i)
{
if (s 0)
{
s += a[i];
}
else
{
s = a[i];
}
if (s r)
Hi,
I didnt understand...can you tell me more details?
thanks,
On Oct 8, 2:27 am, Jun [EMAIL PROTECTED] wrote:
You can first solve the 1-dimension similar problem using DP. That's,
find the maximum sum of continuous sub sequence of an array. Then you
can apply this to 2-dimension problem.
19 matches
Mail list logo
