Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

Solved

Posted on 2003-11-17

Hi,

I have an dinamic array in wich I have random integer elements.

I have to find wich subsequence has the largest multiply value , the index of the first and the last element of this subsequence. i have to do this with no for in for( that is with no for(i=1;i<n;i++) {for j=1;j<n;j++){do something}}).

Example for 2,-5,0,7,8,3,5,-9,-4,0 the result should be 840 from 4 to 7.

Thanx in advance!

I have an dinamic array in wich I have random integer elements.

I have to find wich subsequence has the largest multiply value , the index of the first and the last element of this subsequence. i have to do this with no for in for( that is with no for(i=1;i<n;i++) {for j=1;j<n;j++){do something}}).

Example for 2,-5,0,7,8,3,5,-9,-4,0 the result should be 840 from 4 to 7.

Thanx in advance!

5 Comments

2, -5, 0, 7, 8, 3, 5, -9, -4, 0

the subsequence with the greatest product is 7, 8, 3, 5, -9, -4 (notice: an even number of negative numbers) with a product of 30240. Since theys are all integers the product problem is actually much, much easier than the sum of a subsequence. To do the maximum sum (the solution would work here, too, I think) you should look up dynamic programming in your textbook.

This is much, much easier than that, I believe.

Good luck,

-bcl

You can use one for loop. Inside this loop use a recursive function to find the max multiply value you require.

Keep the array global.

Something like,

for(i=0,......)

{

mulvalue = 1;

ans=func1(mulvalue,i);

}

int func1(int mul,int index)

{

//Store mul in temp variable

//multiply it with array element at position given by index

//check if new value is less than prev, if it is return the value and end

//if new value if greater then call func1 again with mul and index+1

}

I cannot give exact code yet because as jkr said it seems homework.

Dhyanesh

#include <iostream>

using namespace std;

struct Sequence

{

int x;

int y;

int p;

Sequence(int a, int b, int t) : x(a), y(b), p(t) {}

bool operator < (const Sequence& s) { return p < s.p; }

Sequence& operator = (const Sequence& s) { x = s.x; y = s.y; p = s.p; return *this; }

int product(int a[], int x, int y) { int p = a[x]; while (++x <= y) p *= a[x]; return p; }

static Sequence smax;

void findMaxSequence(int a[], int siz)

{

// special case x == 0

if (x == 0 && y < siz - 1)

{

Sequence* psy = new Sequence(x, y + 1, p * a[y + 1]);

if (smax < *psy) smax = *psy;

psy->findMaxSequence(a, siz);

}

if (x < y)

{

int pn = (a[x] != 0)? p / a[x] : product(a, x + 1, y);

Sequence* psx = new Sequence(x + 1, y, pn);

if (smax < *psx) smax = *psx;

psx->findMaxSequence(a, siz);

}

delete this;

}

};

Sequence Sequence::smax(0, 0, 0);

int main( void )

{

int a[] = { 2,-5,0,7,8,3,5,-9,-4,0 };

int siz = sizeof(a) / sizeof(int);

Sequence& smax = Sequence::smax;

smax.p = a[0];

Sequence* ps = new Sequence(0, 0, a[0]);

ps->findMaxSequence(a, siz);

cout << "x=" << smax.x << " y=" << smax.y << " p=" << smax.p << endl;

return 0;

}

Regards, Alex

I will leave the following recommendation for this question in the Cleanup topic area:

Split: bcladd {http:#9765578} & dhyanesh {http:#9769383} & itsmeandnobodyelse {http:#9770802}

Please leave any comments here within the next seven days.

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

Tinchos

EE Cleanup Volunteer

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Course of the Month11 days, 17 hours left to enroll

Join the community of 500,000 technology professionals and ask your questions.