Maximum Linear Stock Score

Maximum Linear Stock Score - Problem

Given a 1-indexed integer array prices, where prices[i] is the price of a particular stock on the ith day, your task is to select some of the elements of prices such that your selection is linear.

A selection indexes, where indexes is a 1-indexed integer array of length k which is a subsequence of the array [1, 2, ..., n], is linear if:

For every 1 < j <= k, prices[indexes[j]] - prices[indexes[j - 1]] == indexes[j] - indexes[j - 1].

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

The score of a selection indexes is equal to the sum of the following array: [prices[indexes[1]], prices[indexes[2]], ..., prices[indexes[k]]].

Return the maximum score that a linear selection can have.

Input & Output

Example 1 — Linear Sequence

$ Input: prices = [1,3,5,7,9]

› Output: 25

💡 Note: The entire array forms a linear sequence with slope 0: (3-1)-(2-1)=1, (5-3)-(3-2)=1, etc. All differences equal the index differences. Sum = 1+3+5+7+9 = 25.

Example 2 — Partial Linear

$ Input: prices = [1,5,3,7,9]

› Output: 16

💡 Note: Best linear subsequence is [1,3,7] at indices [1,3,4]. Check: (3-1)-(3-1)=-0, (7-3)-(4-3)=3. Not linear. Actually [5,7,9] at indices [2,4,5]: (7-5)-(4-2)=0, (9-7)-(5-4)=1. Not linear either. The best is [1,5,9] = 15 or single element sequences. Actually [3,7] has slope (7-3)-(4-3)=3, extending gives [3,7,11] but 11 not in array.

Example 3 — Single Element

$ Input: prices = [10]

› Output: 10

💡 Note: Only one element, so the maximum score is 10.

Constraints

1 ≤ prices.length ≤ 1000
-10⁶ ≤ prices[i] ≤ 10⁶
prices is 1-indexed in the problem description

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that a linear subsequence has constant slope between consecutive points. The optimal approach uses dynamic programming to build sequences incrementally. Time: O(n³), Space: O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Optimization	O(n³)	O(n²)	Use hash map to store linear sequences by their slope and starting point
Dynamic Programming	O(n³)	O(n²)	Use 2D DP where dp[i][j] represents max score of linear sequence ending at i with j as previous element
Brute Force - Check All Subsequences	O(2^n × n)	O(n)	Generate all possible subsequences and check which ones are linear

Hash Map Optimization — Algorithm Steps

For each pair of points (i,j), calculate slope
Use hash map with key (slope, starting_point) to group sequences
Extend existing sequences or start new ones
Track maximum sum across all sequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Slopes

For each pair, compute slope = price_diff - index_diff

Group by Slope

Hash map stores sequences by their slope value

Extend Sequences

Add compatible points to existing sequences

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* prices, int n) {
    if (n == 1) return prices[0];
    
    int maxScore = prices[0];
    for (int i = 1; i < n; i++) {
        maxScore = max(maxScore, prices[i]);
    }
    
    // Simplified approach: check all pairs and try to extend
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int slope = prices[j] - prices[i] - (j - i);
            int currentSum = prices[i] + prices[j];
            maxScore = max(maxScore, currentSum);
            
            // Try to extend this sequence
            for (int k = j + 1; k < n; k++) {
                int expectedDiff = prices[k] - prices[j] - (k - j);
                if (expectedDiff == slope) {
                    currentSum += prices[k];
                    maxScore = max(maxScore, currentSum);
                    j = k;  // Continue from this point
                } else {
                    break;
                }
            }
        }
    }
    
    return maxScore;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int prices[20], n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strcmp(token, "\n") != 0) {
            prices[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(prices, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each pair of points O(n²), we may extend sequences O(n) times

⚠ Quadratic Growth

Space Complexity

O(n²)

Hash map stores sequences for each slope-point combination

⚠ Quadratic Space

8.9K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler