?
Solved

Maximum subsequence multiply

Posted on 2003-11-17
6
Medium Priority
?
1,051 Views
Last Modified: 2010-05-19
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!
0
Comment
Question by:udamsro
[X]
Welcome to Experts Exchange

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
6 Comments
 
LVL 86

Expert Comment

by:jkr
ID: 9764949
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
 
LVL 11

Accepted Solution

by:
bcladd earned 336 total points
ID: 9765578
I don't think your answer is correct. Given the sequence

  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
 
LVL 4

Assisted Solution

by:dhyanesh
dhyanesh earned 332 total points
ID: 9769383
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
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 332 total points
ID: 9770802
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
 
LVL 9

Expert Comment

by:tinchos
ID: 10286310
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}

Please leave any comments here within the next seven days.
PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

Tinchos
EE Cleanup Volunteer
0

Featured Post

New benefit for Premium Members - Upgrade now!

Ready to get started with anonymous questions today? It's easy! Learn more.

Question has a verified solution.

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

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
Suggested Courses

765 members asked questions and received personalized solutions in the past 7 days.

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

Join & Ask a Question