3640. Trionic Array II

/**
 * Problem: LeetCode 3640 - Trionic Array II
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public long maxSumTrionic(int[] nums) {
        int n = nums.length;

        // leftInc[i]: Maximum sum of a strictly increasing subarray ending at index i
        long[] leftInc = new long[n];
        for (int i = 0; i < n; i++) {
            leftInc[i] = nums[i];
            if (i > 0 && nums[i] > nums[i - 1]) {
                leftInc[i] = nums[i] + Math.max(0L, leftInc[i - 1]);
            }
        }

        // rightInc[i]: Maximum sum of a strictly increasing subarray starting at index i
        long[] rightInc = new long[n];
        for (int i = n - 1; i >= 0; i--) {
            rightInc[i] = nums[i];
            if (i + 1 < n && nums[i] < nums[i + 1]) {
                rightInc[i] = nums[i] + Math.max(0L, rightInc[i + 1]);
            }
        }

        long maxSum = Long.MIN_VALUE;
        int i = 0;

        // Traverse all maximal strictly decreasing segments [p...q]
        while (i < n) {
            int j = i;
            while (j + 1 < n && nums[j] > nums[j + 1]) {
                j++;
            }

            if (j > i) {
                int p = i;
                int q = j;

                // Validate transition points:
                // Peak at p requires nums[p - 1] < nums[p]
                // Valley at q requires nums[q] < nums[q + 1]
                if (p > 0 && nums[p - 1] < nums[p] && q + 1 < n && nums[q] < nums[q + 1]) {
                    long decSum = 0;
                    for (int k = p; k <= q; k++) {
                        decSum += nums[k];
                    }

                    long total = leftInc[p - 1] + decSum + rightInc[q + 1];
                    if (total > maxSum) {
                        maxSum = total;
                    }
                }
            }

            i = Math.max(i + 1, j);
        }

        return maxSum;
    }
}

"""
Problem: LeetCode 3640 - Trionic Array II
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def maxSumTrionic(self, nums: List[int]) -> int:
        n = len(nums)

        # left_inc[i]: Maximum sum of a strictly increasing subarray ending at index i
        left_inc = [0] * n
        for i in range(n):
            left_inc[i] = nums[i]
            if i > 0 and nums[i] > nums[i - 1]:
                left_inc[i] = nums[i] + max(0, left_inc[i - 1])

        # right_inc[i]: Maximum sum of a strictly increasing subarray starting at index i
        right_inc = [0] * n
        for i in range(n - 1, -1, -1):
            right_inc[i] = nums[i]
            if i + 1 < n and nums[i] < nums[i + 1]:
                right_inc[i] = nums[i] + max(0, right_inc[i + 1])

        max_sum = float('-inf')
        i = 0

        # Traverse all maximal strictly decreasing segments [p...q]
        while i < n:
            j = i
            while j + 1 < n and nums[j] > nums[j + 1]:
                j += 1

            if j > i:
                p, q = i, j
                # Peak at p requires nums[p - 1] < nums[p]
                # Valley at q requires nums[q] < nums[q + 1]
                if p > 0 and nums[p - 1] < nums[p] and q + 1 < n and nums[q] < nums[q + 1]:
                    dec_sum = sum(nums[p:q + 1])
                    total = left_inc[p - 1] + dec_sum + right_inc[q + 1]
                    if total > max_sum:
                        max_sum = total

            i = max(i + 1, j)

        return max_sum

/**
 * Problem: LeetCode 3640 - Trionic Array II
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

class Solution {
public:
    long long maxSumTrionic(vector<int>& nums) {
        int n = nums.size();

        // leftInc[i]: Maximum sum of a strictly increasing subarray ending at index i
        vector<long long> leftInc(n);
        for (int i = 0; i < n; i++) {
            leftInc[i] = nums[i];
            if (i > 0 && nums[i] > nums[i - 1]) {
                leftInc[i] = nums[i] + max(0LL, leftInc[i - 1]);
            }
        }

        // rightInc[i]: Maximum sum of a strictly increasing subarray starting at index i
        vector<long long> rightInc(n);
        for (int i = n - 1; i >= 0; i--) {
            rightInc[i] = nums[i];
            if (i + 1 < n && nums[i] < nums[i + 1]) {
                rightInc[i] = nums[i] + max(0LL, rightInc[i + 1]);
            }
        }

        long long maxSum = LLONG_MIN;
        int i = 0;

        // Traverse all maximal strictly decreasing segments [p...q]
        while (i < n) {
            int j = i;
            while (j + 1 < n && nums[j] > nums[j + 1]) {
                j++;
            }

            if (j > i) {
                int p = i;
                int q = j;

                // Peak at p requires nums[p - 1] < nums[p]
                // Valley at q requires nums[q] < nums[q + 1]
                if (p > 0 && nums[p - 1] < nums[p] && q + 1 < n && nums[q] < nums[q + 1]) {
                    long long decSum = 0;
                    for (int k = p; k <= q; k++) {
                        decSum += nums[k];
                    }

                    long long total = leftInc[p - 1] + decSum + rightInc[q + 1];
                    if (total > maxSum) {
                        maxSum = total;
                    }
                }
            }

            i = max(i + 1, j);
        }

        return maxSum;
    }
};

/**
 * Problem: LeetCode 3640 - Trionic Array II
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSumTrionic = function(nums) {
    const n = nums.length;

    // leftInc[i]: Maximum sum of a strictly increasing subarray ending at index i
    const leftInc = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        leftInc[i] = nums[i];
        if (i > 0 && nums[i] > nums[i - 1]) {
            leftInc[i] = nums[i] + Math.max(0, leftInc[i - 1]);
        }
    }

    // rightInc[i]: Maximum sum of a strictly increasing subarray starting at index i
    const rightInc = new Array(n).fill(0);
    for (let i = n - 1; i >= 0; i--) {
        rightInc[i] = nums[i];
        if (i + 1 < n && nums[i] < nums[i + 1]) {
            rightInc[i] = nums[i] + Math.max(0, rightInc[i + 1]);
        }
    }

    let maxSum = -Infinity;
    let i = 0;

    // Traverse all maximal strictly decreasing segments [p...q]
    while (i < n) {
        let j = i;
        while (j + 1 < n && nums[j] > nums[j + 1]) {
            j++;
        }

        if (j > i) {
            const p = i;
            const q = j;

            // Peak at p requires nums[p - 1] < nums[p]
            // Valley at q requires nums[q] < nums[q + 1]
            if (p > 0 && nums[p - 1] < nums[p] && q + 1 < n && nums[q] < nums[q + 1]) {
                let decSum = 0;
                for (let k = p; k <= q; k++) {
                    decSum += nums[k];
                }

                const total = leftInc[p - 1] + decSum + rightInc[q + 1];
                if (total > maxSum) {
                    maxSum = total;
                }
            }
        }

        i = Math.max(i + 1, j);
    }

    return maxSum;
};