• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1054
  • Last Modified:

Maximum subsequence multiply

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!
3 Solutions
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)
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,

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,

      mulvalue = 1;

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.

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

EE Cleanup Volunteer

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now