Solved

Maximum subsequence multiply

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

Secure Your Active Directory - April 20, 2017

Active Directory plays a critical role in your company’s IT infrastructure and keeping it secure in today’s hacker-infested world is a must.
Microsoft published 300+ pages of guidance, but who has the time, money, and resources to implement? Register now to find an easier way.

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…
In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
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 how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

730 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