Solved

Maximum subsequence multiply

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

Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

Question has a verified solution.

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

Suggested Solutions

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

776 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