How do I find the maximum element of a contiguous subsequence of an array of integers as fast as possible? Suppose there are multiple queries for the same array but with different subsequences, is there a way to use Dynamic Programming to store the maximum value of a sequence based on its contiguous subsequences?

I tried using something similar to Kadane’s algorithm which computed the maximum sum of contiguous subsequences thus having O(n) time complexity for n-size arrays and k queries but i realized that getting the max element for each subseq ending in each index doesn’t contribute to the maximum value of the next index.

The standard way of doing this would have O(n*k) time complexity for n-size arrays and k queries of finding the maximum of contiguous subsequence of the array.