# Maximum subsequence multiply

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.
###### Who is Participating?

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
Hm, you would get all possible subsequences by calculating all the permutations of start/end pairs (see 'next_permutation()'), iterate through them using vector iterators to calculate the multiply value, store the results in a container and sort it. As I assume that this is homework, I cannot really be more specific :o)
0
Commented:

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
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
hi

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
0
Commented:
Try this:

#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
0
Commented:
No comment has been added lately, so it's time to clean up this TA.
I will leave the following recommendation for this question in the Cleanup topic area:

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