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