2
$\begingroup$

I am aware of how to solve maximum contiguous sub sequence given different constraints (increasing, sum, product, etc). However, I'm having problems with trying to satisfy the following constraint.

I want to the sub sequence with the largest $X$ where $X$ is defined as the product of the sub seq length and the largest val in the sub seq.

I tried a small test case with 4 numbers: {1, 10, 10, 1}. The largest sequence would be in the middle with {10, 10} as this gives an $X$ value of 20. To approach this, I'd break the sequence down the middle into two groups. The largest $X$ on each side can be obtained by simply $max(sequence)*length$ on each side. But how do I traverse through the middle efficiently?

$\endgroup$

1 Answer 1

-1
$\begingroup$

I see that you do a divide and conquer method but that’s do not work ,if I understand it properly ,because if you take {10,10,1} ,X will be 30. My solution will be that you traverse the list, find the maximum element and the maximum subsequence will be the subsequence with the last n-1 elements if the max is not the first element and if the max is the first it’s the first n-1 elements . So you will have the maximum X.

$\endgroup$
4
  • $\begingroup$ When you divide and conquer, you don't have to split in the middle, you can split at the minimum value which will work. $\endgroup$
    – Jonathan
    Oct 1, 2018 at 20:20
  • $\begingroup$ Because probably there is a misunderstanding can you explain that? $\endgroup$
    – ManosL
    Oct 1, 2018 at 20:23
  • $\begingroup$ Wair sorry, yes your algorithm is right $\endgroup$
    – Jonathan
    Oct 1, 2018 at 20:24
  • $\begingroup$ Wait a minute, the product is the maximum element multiplied with the times that occurs? If finally I am right as you edited , plz upvote me 😛 $\endgroup$
    – ManosL
    Oct 1, 2018 at 20:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .