A robust methodology for contiguous range problems relies on defining dp[k] as the optimal metric for subsegments terminating exactly at index k. By evaluating whether to extend the previous segment or reset at the current positino, we derive efficient recurrence relations. Below is a systematic breakdown of eight fundamental variations.

Maximum Contiguous Sum

State Definition: end_at_idx tracks the highest sum achievable for a segment ending at the current index. Transition: At each element, decide whether to merge with the prior sequence or start fresh: current = max(arr[idx], prev + arr[idx]). Execution: Iterate forward, maintaining a running maximum across all positions.

class Solution {
public:
    int findMaxSum(const std::vector<int>& arr) {
        int n = arr.size();
        std::vector<int> end_at_idx(n);
        end_at_idx[0] = arr[0];
        int global_best = arr[0];
        
        for (int i = 1; i < n; ++i) {
            end_at_idx[i] = std::max(arr[i], end_at_idx[i-1] + arr[i]);
            global_best = std::max(global_best, end_at_idx[i]);
        }
        return global_best;
    }
};

Circular Segment Optimization

When boundaries wrap around, the optimal segment either lies entirely within the linear bounds or spans across the array ends. The latter corresponds to the total sum minus the minimum contiguous sum found in the middle. We maintain parallel tracking variables for both extremes.

class Solution {
public:
    int solveCircularMax(const std::vector<int>& arr) {
        int total_sum = 0;
        int cur_max = 0, max_so_far = INT_MIN;
        int cur_min = 0, min_so_far = INT_MAX;
        
        for (int x : arr) {
            total_sum += x;
            cur_max = std::max(x, cur_max + x);
            max_so_far = std::max(max_so_far, cur_max);
            
            cur_min = std::min(x, cur_min + x);
            min_so_far = std::min(min_so_far, cur_min);
        }
        
        if (max_so_far < 0) return max_so_far;
        return std::max(max_so_far, total_sum - min_so_far);
    }
};

Maximum Product Range

Multiplication introduces sign flips, requiring simultaneous tracking of positive and negative extrema. A negative multiplier can turn a minimum into a maximum.

class Solution {
public:
    int maxProductSequence(const std::vector<int>& arr) {
        int n = arr.size();
        std::vector<int> prod_max(n), prod_min(n);
        prod_max[0] = arr[0];
        prod_min[0] = arr[0];
        int res = arr[0];
        
        for (int i = 1; i < n; ++i) {
            if (arr[i] < 0) std::swap(prod_max[i-1], prod_min[i-1]);
            prod_max[i] = std::max(arr[i], prod_max[i-1] * arr[i]);
            prod_min[i] = std::min(arr[i], prod_min[i-1] * arr[i]);
            res = std::max(res, prod_max[i]);
        }
        return res;
    }
};

Extended Length with Positive Result

To maximize array length under a positivity constraint, store separate counters for sequences yielding positive versus negative outcomes.

class Solution {
public:
    int longestPositiveLength(const std::vector<int>& arr) {
        int n = arr.size();
        std::vector<int> pos_len(n, 0), neg_len(n, 0);
        int ans = 0;
        
        for (int i = 0; i < n; ++i) {
            if (arr[i] > 0) {
                pos_len[i] = pos_len[i-1] + 1;
                neg_len[i] = neg_len[i-1] ? neg_len[i-1] + 1 : 0;
            } else if (arr[i] < 0) {
                pos_len[i] = neg_len[i-1] ? neg_len[i-1] + 1 : 0;
                neg_len[i] = pos_len[i-1] + 1;
            }
            ans = std::max(ans, pos_len[i]);
        }
        return ans;
    }
};

Counting Arithmetic Segments

A contiguous arithmetic progression extends naturally. If arr[i] - arr[i-1] == arr[i-1] - arr[i-2], the count of valid slices ending at i increases by one relative to i-1.

class Solution {
public:
    int countArithmeticRanges(const std::vector<int>& arr) {
        int n = arr.size();
        if (n < 3) return 0;
        
        std::vector<int> cnt(n, 0);
        int total_slices = 0;
        
        for (int i = 2; i < n; ++i) {
            if (arr[i] - arr[i-1] == arr[i-1] - arr[i-2]) {
                cnt[i] = cnt[i-1] + 1;
                total_slices += cnt[i];
            }
        }
        return total_slices;
    }
};

Peak-to-Trough Oscillation Length

Turbulent sequences alternate direction. We maintain two trackers: one for ascending steps and another for descending steps ending at the current endex.

class Solution {
public:
    int maxOscillationSize(const std::vector<int>& arr) {
        int n = arr.size();
        std::vector<int> asc_len(n, 1), desc_len(n, 1);
        
        for (int i = 1; i < n; ++i) {
            if (arr[i] > arr[i-1]) asc_len[i] = desc_len[i-1] + 1;
            else if (arr[i] < arr[i-1]) desc_len[i] = asc_len[i-1] + 1;
        }
        
        return std::max(*std::max_element(asc_len.begin(), asc_len.end()),
                        *std::max_element(desc_len.begin(), desc_len.end()));
    }
};

Lexical Segment Validation

Determine if a string can be partitioned into dictionary entries. The boolean state valid_prefix[k] indicates whether the substring from start to k forms a valid concatenation.

class Solution {
public:
    bool checkPartitioning(const std::string& s, const std::vector<std::string>& dict) {
        std::unordered_set<std::string> lookup(dict.begin(), dict.end());
        int n = s.length();
        std::vector<bool> valid_prefix(n + 1, false);
        valid_prefix[0] = true;
        
        for (int i = 1; i <= n; ++i) {
            for (int j = i; j >= 1; --j) {
                if (valid_prefix[j-1] && lookup.count(s.substr(j-1, i-j+1))) {
                    valid_prefix[i] = true;
                    break;
                }
            }
        }
        return valid_prefix[n];
    }
};

Rotated Sequence Frequency

Count distinct valid substrings in a cyclic alphabet sequence. Instead of storing raw counts, aggregate by the terminating character. For each character, only the longest valid chain matters.

class Solution {
public:
    int countWraparoundFreq(const std::string& s) {
        std::vector<int> char_max(26, 0);
        int curr_run = 0;
        
        for (int i = 0; i < s.size(); ++i) {
            if (i > 0 && (s[i-1] + 1 == s[i] || (s[i-1] == 'z' && s[i] == 'a'))) {
                curr_run++;
            } else {
                curr_run = 1;
            }
            char_max[s[i] - 'a'] = std::max(char_max[s[i] - 'a'], curr_run);
        }
        
        return std::accumulate(char_max.begin(), char_max.end(), 0);
    }
};