Given a sequence of stones with non-negative integers, calculate the maximum possible score starting from the beginning to end. You can jump any number of positions from each position. The score is calculated as the destination stone_value * number_of_jump_positions. Essentially the first value in the array doesn't matter as you always jump from beginning and only the destination stone value is considered in the score computation. You need to solve it in less than O(n^2) time.

I could come up with O(n^2) solution but couldn't solve it in less than that time complexity. Any ideas leetcoders?

For example,
Test case 1: Stones = [1, 2, 3, 4, 5], Maximum total score = 20 #you jump to ast position, so the score would be 5 * 4 = 20
Test case 2: Stones = [5, 4, 3, 2, 1], Maximum total score = 10 #you jump one position from beginning to end, so the score would be 4+3+2+1=10
Test case 3: Stones = [2, 4, 6, 8, 10], Maximum total score = 40
Test case 4: Stones = [3, 5, 2, 8, 1], Maximum total score = 25
Test case 5: Stones = [1, 1, 1, 1, 1], Maximum total score = 4
Test case 6: Stones = [5, 3, 5, 3, 5], Maximum total score = 20

def max_score(input):
    dp = [0] * len(input)
    for i in range(1, len(input)):
        for j in range(i):
            dp[i] = max(dp[j]+(input[i]*(i-j)), dp[i])
    return dp[-1]

# Test cases
test_cases = [
    [1, 2, 3, 4, 5],  # Example test case
    [5, 4, 3, 2, 1],  # Reverse order
    [2, 4, 6, 8, 10],  # Even numbers
    [3, 5, 2, 8, 1],  # Random order
    [1, 1, 1, 1, 1],  # All equal
    [5, 3, 5, 3, 5]   # Alternating
]

# Run test cases
for i, stones in enumerate(test_cases):
    max_total_score = max_score(stones)
    print(f"Test case {i+1}: Stones = {stones}, Maximum total score = {max_total_score}")