# Re: Puzzle

Discussion in 'C Programming' started by Kevin D. Quitt, Jul 29, 2003.

1. ### Kevin D. QuittGuest

--
#include <standard.disclaimer>
_
Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
Per the FCA, this address may not be added to any commercial mail list

Kevin D. Quitt, Jul 29, 2003

2. ### RamgopalGuest

Jeez !!
Ppl take immediate offense to a puzzle ..
Some clarifications:
Its not part of my homework. I was just browsing through some
Microsoft interview Qs and got stumped over this one. Agreed I might
be low on the IQ front but just to prove my homework
Understanding the problem -
To figure out the sum of the elements of those ordered sub-sets of the
set {X1,..,Xn} such that:
for any sub-set {Xi,..,Xj}, (i < j) && ((j - i) = Cardinality of
{Xi,..,Xj}).
Soln to the problem -
This boils down to running two nested for loops as we do in case of
bubble sort.

But I am still looking for the O(N) algo.
~RG
ps -> Spare me for the mistakes in the formal notations. I am not good
at them.

Ramgopal, Jul 30, 2003

3. ### Alf P. SteinbachGuest

On 29 Jul 2003 21:32:37 -0700, (Ramgopal) wrote:

>Jeez !!
>Ppl take immediate offense to a puzzle ..

To a question for a solution to obvious homework.

>Some clarifications:
>Its not part of my homework. I was just browsing through some
>Microsoft interview Qs and got stumped over this one. Agreed I might
>be low on the IQ front but just to prove my homework
>Understanding the problem -
>To figure out the sum of the elements of those ordered sub-sets of the
>set {X1,..,Xn} such that:
>for any sub-set {Xi,..,Xj}, (i < j) && ((j - i) = Cardinality of
>{Xi,..,Xj}).
>Soln to the problem -
>This boils down to running two nested for loops as we do in case of
>bubble sort.
>
>But I am still looking for the O(N) algo.

I already gave you a very strong hint.

Alf P. Steinbach, Jul 30, 2003
4. ### MGGuest

> To figure out the sum of the elements of those ordered sub-sets of the
> set {X1,..,Xn} such that:
> for any sub-set {Xi,..,Xj}, (i < j) && ((j - i) = Cardinality of
> {Xi,..,Xj}).

I assume the cardinality is known ( say m)

> Soln to the problem -
> This boils down to running two nested for loops as we do in case of
> bubble sort.

why do u need 2 loops??
u need to add the m number starting from index 0, and keep a track of the
sum and the index of the substring corresponding to that sum...
then use sliding window protocol...and at each step...compare the values of
the sum...and update the sum and the index pointer as required.....

by the end of the loop...u know the index of the sub aray which has the
maximum sum..

> But I am still looking for the O(N) algo.

this takes O(N)

HTH
manish

MG, Jul 30, 2003
5. ### Default UserGuest

Ramgopal wrote:
>
> Jeez !!
> Ppl take immediate offense to a puzzle ..

Where did you get the idea that we are interested in random people
quizzing us? Most of us have plenty of real puzzles in our everyday work
to keep up occupied. If a problem interests you, work it out yourself
and post your solution. We'll be happy to comment on that.

Brian Rodenborn

Default User, Jul 30, 2003
6. ### Kevin EastonGuest

Ramgopal <> wrote:
> Jeez !!
> Ppl take immediate offense to a puzzle ..
> Some clarifications:
> Its not part of my homework. I was just browsing through some
> Microsoft interview Qs and got stumped over this one. Agreed I might
> be low on the IQ front but just to prove my homework
> I had figured out a soln already. But it was O(N^2).
> Understanding the problem -
> To figure out the sum of the elements of those ordered sub-sets of the
> set {X1,..,Xn} such that:
> for any sub-set {Xi,..,Xj}, (i < j) && ((j - i) = Cardinality of
> {Xi,..,Xj}).
> Soln to the problem -
> This boils down to running two nested for loops as we do in case of
> bubble sort.
>
> But I am still looking for the O(N) algo.
> ~RG
> ps -> Spare me for the mistakes in the formal notations. I am not good
> at them.

The solution is something like this (this works, except for the edge-cases,
like an empty array or an array composed entirely of negative numbers -
you'll have to modify it a bit to get those right, but you get the
general idea):

struct subarray {
size_t left, right;
};

void maxsubarray(struct subarray *result, int array[], size_t arraylen)
{
size_t max_l, max_r;
size_t cur_l;
int maxsum = 0;
int cursum = 0;
size_t i;

for (max_l = 0, max_r = 0, cur_l = 0, i = 0; i < arraylen; i++) {
cursum += array;
if (cursum < 0) {
cursum = 0;
cur_l = i + 1;
} else if (cursum > maxsum) {
maxsum = cursum;
max_l = cur_l;
max_r = i;
}
}

result->left = max_l;
result->right = max_r;
}

- Kevin.

Kevin Easton, Jul 30, 2003