Solved

Maximum subsequence multiply

Posted on 2003-11-17
6
1,048 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 84 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 83 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 83 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

Enroll in June's Course of the Month

June’s Course of the Month is now available! Experts Exchange’s Premium Members, Team Accounts, and Qualified Experts have access to a complimentary course each month as part of their membership—an extra way to sharpen your skills and increase training.

Question has a verified solution.

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

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
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…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

691 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