Dynamic programming solutions for contiguous subarray challenges typically analyze sequences where each element serves as the endpoint of potential subarrays. This approach efficiently leverages overlapping subproblems and optimal substructure properties.

Maximum Subarray Sum

Finding the largest sum of any contiguous subarray uses Kadane's algorithm, tracking curent and global maximum sums during iteration.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int current = nums[0];
        int best = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            current = max(nums[i], current + nums[i]);
            best = max(best, current);
        }
        return best;
    }
};

Circular Subarray Maximum Sum

For circular arrays, the solution compares the standard maximum subarray sum with the total sum minus the minimum subarray sum, handling edge cases where all elements are negative.

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int total = 0, max_sum = nums[0], current_max = 0, min_sum = nums[0], current_min = 0;
        for (int num : nums) {
            total += num;
            current_max = max(num, current_max + num);
            max_sum = max(max_sum, current_max);
            current_min = min(num, current_min + num);
            min_sum = min(min_sum, current_min);
        }
        return max_sum > 0 ? max(max_sum, total - min_sum) : max_sum;
    }
};

Maximum Product Subarray

Tracking both maximum and minimum products at each step handles negative values that can transform minimum products into maximum products upon multiplication.

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.empty()) return 0;
        int current_max = nums[0];
        int current_min = nums[0];
        int result = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            int temp = current_max;
            current_max = max({nums[i], current_max * nums[i], current_min * nums[i]});
            current_min = min({nums[i], temp * nums[i], current_min * nums[i]});
            result = max(result, current_max);
        }
        return result;
    }
};

Longest Positive Product Subarray

Separate counters for positive and negative sequence lengths enable efficient tracking of valid subarrays where product remains positive.

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int pos = 0, neg = 0;
        int max_length = 0;
        for (int num : nums) {
            if (num > 0) {
                pos = pos + 1;
                neg = neg > 0 ? neg + 1 : 0;
            } else if (num < 0) {
                int prev_pos = pos;
                pos = neg > 0 ? neg + 1 : 0;
                neg = prev_pos + 1;
            } else {
                pos = neg = 0;
            }
            max_length = max(max_length, pos);
        }
        return max_length;
    }
};

Arithmetic Slices

Counting contiguous arithmetic sequences involves tracking current streaks of valid sequences and accumulating counts during iteration.

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        if (nums.size() < 3) return 0;
        int current = 0;
        int total = 0;
        for (int i = 2; i < nums.size(); ++i) {
            if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                current += 1;
                total += current;
            } else {
                current = 0;
            }
        }
        return total;
    }
};

Longest Turbulent Subarray

Alternating up/down sequences are tracked using separate counters for increasing and decreasing patterns at each position.

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int up = 1, down = 1;
        int max_len = 1;
        for (int i = 1; i < arr.size(); ++i) {
            if (arr[i] > arr[i-1]) {
                up = down + 1;
                down = 1;
            } else if (arr[i] < arr[i-1]) {
                down = up + 1;
                up = 1;
            } else {
                up = down = 1;
            }
            max_len = max(max_len, max(up, down));
        }
        return max_len;
    }
};

Word Break

Determining if a string can be segmented into dictionary words uses a DP array to track valid segmentations up to each index.

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && dict.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp.back();
    }
};

Wrapped String Substrings

Counting unique substrings in a circular alphabet uses per-character maximum sequence lengths to aggregate results efficiently.

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