MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

- Help others & share knowledge
- Earn cash & points
- Learn & ask questions

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!

6 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.

If you are experiencing a similar issue, please ask a related question

Title | # Comments | Views | Activity |
---|---|---|---|

Websocket through haproxy reused connection causes "Not a valid frame" error. | 4 | 106 | |

VS2015 Redefinition errors | 4 | 67 | |

draw a Christmas tree by using a nested loop? | 26 | 75 | |

HTTPSendRequest with WinINet delays on first call | 11 | 29 |

The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

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