给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。

回想一下：

• 叶节点 是二叉树中没有子节点的节点
• 树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
• 如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 6、0 和 8 也是叶节点，但是它们的深度是 2 ，而节点 7 和 4 的深度是 3 。

示例 2：

输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点，它是它本身的最近公共祖先。

示例 3：

输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的叶节点是 2 ，最近公共祖先是它自己。

提示：

• 树中的节点数将在 [1, 1000] 的范围内。
• 0 <= Node.val <= 1000
• 每个节点的值都是 独一无二 的。

注意：本题与力扣 865 重复：https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/

推荐先看 二叉树的最近公共祖先【基础算法精讲 12】，对于理解本题做法有帮助。

方法一：递归递归，有递有归

看上图（示例 1），这棵树的节点 $3,5,2$ 都是最深叶节点 $7,4$ 的公共祖先，但只有节点 $2$ 是最近的公共祖先。

上面视频中提到，如果我们要找的节点只在左子树中，那么最近公共祖先也必然只在左子树中。对于本题，如果左子树的最大深度比右子树的大，那么最深叶结点就只在左子树中，所以最近公共祖先也只在左子树中。

如果左右子树的最大深度一样呢？当前节点一定是最近公共祖先吗？

不一定。比如节点 $1$ 的左右子树最深叶节点 $0,8$ 的深度都是 $2$，但该深度并不是全局最大深度，所以节点 $1$ 并不能是答案。

根据以上讨论，正确做法如下：

1. 递归这棵二叉树，同时维护全局最大深度 $\textit{maxDepth}$。
2. 在「递」的时候往下传 $\textit{depth}$，用来表示当前节点的深度。
3. 在「归」的时候往上传当前子树最深叶节点的深度。
4. 设左子树最深叶节点的深度为 $\textit{leftMaxDepth}$，右子树最深叶节点的深度为 $\textit{rightMaxDepth}$。如果 $\textit{leftMaxDepth}=\textit{rightMaxDepth}=\textit{maxDepth}$，那么更新答案为当前节点。注意这并不代表我们找到了答案，如果后面发现了更深的叶节点，那么答案还会更新。

class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        ans = None
        max_depth = -1  # 全局最大深度
        def dfs(node: Optional[TreeNode], depth: int) -> int:
            nonlocal ans, max_depth
            if node is None:
                max_depth = max(max_depth, depth)  # 维护全局最大深度
                return depth
            left_max_depth = dfs(node.left, depth + 1)  # 获取左子树最深叶节点的深度
            right_max_depth = dfs(node.right, depth + 1)  # 获取右子树最深叶节点的深度
            if left_max_depth == right_max_depth == max_depth:
                ans = node
            return max(left_max_depth, right_max_depth)  # 当前子树最深叶节点的深度
        dfs(root, 0)
        return ans

class Solution {
    private TreeNode ans;
    private int maxDepth = -1; // 全局最大深度

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    private int dfs(TreeNode node, int depth) {
        if (node == null) {
            maxDepth = Math.max(maxDepth, depth); // 维护全局最大深度
            return depth;
        }
        int leftMaxDepth = dfs(node.left, depth + 1); // 获取左子树最深叶节点的深度
        int rightMaxDepth = dfs(node.right, depth + 1); // 获取右子树最深叶节点的深度
        if (leftMaxDepth == rightMaxDepth && leftMaxDepth == maxDepth)
            ans = node;
        return Math.max(leftMaxDepth, rightMaxDepth); // 当前子树最深叶节点的深度
    }
}

class Solution {
public:
    TreeNode *lcaDeepestLeaves(TreeNode *root) {
        TreeNode *ans = nullptr;
        int max_depth = -1; // 全局最大深度
        function<int(TreeNode*, int)> dfs = [&](TreeNode *node, int depth) {
            if (node == nullptr) {
                max_depth = max(max_depth, depth); // 维护全局最大深度
                return depth;
            }
            int left_max_depth = dfs(node->left, depth + 1); // 获取左子树最深叶节点的深度
            int right_max_depth = dfs(node->right, depth + 1); // 获取右子树最深叶节点的深度
            if (left_max_depth == right_max_depth && left_max_depth == max_depth)
                ans = node;
            return max(left_max_depth, right_max_depth); // 当前子树最深叶节点的深度
        };
        dfs(root, 0);
        return ans;
    }
};

func lcaDeepestLeaves(root *TreeNode) (ans *TreeNode) {
    maxDepth := -1 // 全局最大深度
    var dfs func(*TreeNode, int) int
    dfs = func(node *TreeNode, depth int) int {
        if node == nil {
            maxDepth = max(maxDepth, depth) // 维护全局最大深度
            return depth
        }
        leftMaxDepth := dfs(node.Left, depth+1) // 获取左子树最深叶节点的深度
        rightMaxDepth := dfs(node.Right, depth+1) // 获取右子树最深叶节点的深度
        if leftMaxDepth == rightMaxDepth && leftMaxDepth == maxDepth {
            ans = node
        }
        return max(leftMaxDepth, rightMaxDepth) // 当前子树最深叶节点的深度
    }
    dfs(root, 0)
    return
}

func max(a, b int) int { if b > a { return b }; return a }

var lcaDeepestLeaves = function (root) {
    let ans = null;
    let maxDepth = -1; // 全局最大深度
    function dfs(node, depth) {
        if (node === null) {
            maxDepth = Math.max(maxDepth, depth); // 维护全局最大深度
            return depth;
        }
        const leftMaxDepth = dfs(node.left, depth + 1); // 获取左子树最深叶节点的深度
        const rightMaxDepth = dfs(node.right, depth + 1); // 获取右子树最深叶节点的深度
        if (leftMaxDepth === rightMaxDepth && leftMaxDepth === maxDepth)
            ans = node;
        return Math.max(leftMaxDepth, rightMaxDepth);// 当前子树最深叶节点的深度
    }
    dfs(root, 0);
    return ans;
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$。每个节点都会恰好访问一次。
• 空间复杂度：$\mathcal{O}(n)$。最坏情况下，二叉树是一条链，递归需要 $\mathcal{O}(n)$ 的栈空间。

方法二：自底向上

也可以不用全局变量，而是把每棵子树都看成是一个「子问题」，即对于每棵子树，我们需要知道：

• 这棵子树最深叶结点的深度。这里是指叶子在这棵子树内的深度，而不是在整棵二叉树的视角下的深度。相当于这棵子树的高度。
• 这棵子树的最深叶结点的最近公共祖先 $\textit{lca}$。

分类讨论：

• 设子树的根节点为 $\textit{node}$，$\textit{node}$ 的左子树的高度为 $\textit{leftHeight}$，$\textit{node}$ 的右子树的高度为 $\textit{rightHeight}$。
• 如果 $\textit{leftHeight} > \textit{rightHeight}$，那么子树的高度为 $\textit{leftHeight} + 1$，$\textit{lca}$ 是左子树的 $\textit{lca}$。
• 如果 $\textit{leftHeight} < \textit{rightHeight}$，那么子树的高度为 $\textit{rightHeight} + 1$，$\textit{lca}$ 是右子树的 $\textit{lca}$。
• 如果 $\textit{leftHeight} = \textit{rightHeight}$，那么子树的高度为 $\textit{leftHeight} + 1$，$\textit{lca}$ 就是 $\textit{node}$。反证法：如果 $\textit{lca}$ 在左子树中，那么 $\textit{lca}$ 不是右子树的最深叶结点的祖先，这不对；如果 $\textit{lca}$ 在右子树中，那么 $\textit{lca}$ 不是左子树的最深叶结点的祖先，这也不对；如果 $\textit{lca}$ 在 $\textit{node}$ 的上面，那就不符合「最近」的要求。所以 $\textit{lca}$ 只能是 $\textit{node}$。

class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node: Optional[TreeNode]) -> (int, Optional[TreeNode]):
            if node is None:
                return 0, None
            left_height, left_lca = dfs(node.left)
            right_height, right_lca = dfs(node.right)
            if left_height > right_height:  # 左子树更高
                return left_height + 1, left_lca
            if left_height < right_height:  # 右子树更高
                return right_height + 1, right_lca
            return left_height + 1, node  # 一样高
        return dfs(root)[1]

class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        return dfs(root).getValue();
    }

    private Pair<Integer, TreeNode> dfs(TreeNode node) {
        if (node == null)
            return new Pair<>(0, null);
        var left = dfs(node.left);
        var right = dfs(node.right);
        if (left.getKey() > right.getKey()) // 左子树更高
            return new Pair<>(left.getKey() + 1, left.getValue());
        if (left.getKey() < right.getKey()) // 右子树更高
            return new Pair<>(right.getKey() + 1, right.getValue());
        return new Pair<>(left.getKey() + 1, node); // 一样高
    }
}

class Solution {
    pair<int, TreeNode*> dfs(TreeNode *node) {
        if (node == nullptr)
            return {0, nullptr};
        auto [left_height, left_lca] = dfs(node->left);
        auto [right_height, right_lca] = dfs(node->right);
        if (left_height > right_height) // 左子树更高
            return {left_height + 1, left_lca};
        if (left_height < right_height) // 右子树更高
            return {right_height + 1, right_lca};
        return {left_height + 1, node}; // 一样高
    }

public:
    TreeNode *lcaDeepestLeaves(TreeNode *root) {
        return dfs(root).second;
    }
};

func dfs(node *TreeNode) (int, *TreeNode) {
    if node == nil {
        return 0, nil
    }
    leftHeight, leftLCA := dfs(node.Left)
    rightHeight, rightLCA := dfs(node.Right)
    if leftHeight > rightHeight { // 左子树更高
        return leftHeight + 1, leftLCA
    }
    if leftHeight < rightHeight { // 右子树更高
        return rightHeight + 1, rightLCA
    }
    return leftHeight + 1, node // 一样高
}

func lcaDeepestLeaves(root *TreeNode) *TreeNode {
    _, lca := dfs(root)
    return lca
}

var dfs = function (node) {
    if (node === null)
        return [0, null];
    const [leftHeight, leftLca] = dfs(node.left);
    const [rightHeight, rightLca] = dfs(node.right);
    if (leftHeight > rightHeight) // 左子树更高
        return [leftHeight + 1, leftLca];
    if (leftHeight < rightHeight) // 右子树更高
        return [rightHeight + 1, rightLca];
    return [leftHeight + 1, node]; // 一样高
};

var lcaDeepestLeaves = function (root) {
    return dfs(root, 0)[1];
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$。每个节点都会恰好访问一次。
• 空间复杂度：$\mathcal{O}(n)$。最坏情况下，二叉树是一条链，递归需要 $\mathcal{O}(n)$ 的栈空间。

练习

• 104. 二叉树的最大深度
• 236. 二叉树的最近公共祖先
• 235. 二叉搜索树的最近公共祖先
• 2096. 从二叉树一个节点到另一个节点每一步的方向

我的其它题解（按 tag 分类）

方法一：递归

思路与算法

题目给出一个二叉树，要求返回它最深的叶节点的最近公共祖先。其中树的根节点的深度为 $0$，我们注意到所有深度最大的节点，都是树的叶节点。为方便说明，我们把最深的叶节点的最近公共祖先，称之为 $\textit{lca}$ 节点。

我们用递归的方式，进行深度优先搜索，对树中的每个节点进行递归，返回当前子树的最大深度 $d$ 和 $\textit{lca}$ 节点。如果当前节点为空，我们返回深度 $0$ 和空节点。在每次搜索中，我们递归地搜索左子树和右子树，然后比较左右子树的深度：

• 如果左子树更深，最深叶节点在左子树中，我们返回 {左子树深度 + $1$，左子树的 $\textit{lca}$ 节点}
• 如果右子树更深，最深叶节点在右子树中，我们返回 {右子树深度 + $1$，右子树的 $\textit{lca}$ 节点}
• 如果左右子树一样深，左右子树都有最深叶节点，我们返回 {左子树深度 + $1$，当前节点}

最后我们返回根节点的 $\textit{lca}$ 节点即可。

代码

###C++

class Solution {
public:
    pair<TreeNode*, int> f(TreeNode* root) {
        if (!root) {
            return {root, 0};
        }

        auto left = f(root->left);
        auto right = f(root->right);

        if (left.second > right.second) {
            return {left.first, left.second + 1};
        }
        if (left.second < right.second) {
            return {right.first, right.second + 1};
        }
        return {root, left.second + 1};

    }

    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        return f(root).first;
    }
};

###Java

class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        return f(root).getKey();
    }

    private Pair<TreeNode, Integer> f(TreeNode root) {
        if (root == null) {
            return new Pair<>(root, 0);
        }

        Pair<TreeNode, Integer> left = f(root.left);
        Pair<TreeNode, Integer> right = f(root.right);

        if (left.getValue() > right.getValue()) {
            return new Pair<>(left.getKey(), left.getValue() + 1);
        }
        if (left.getValue() < right.getValue()) {
            return new Pair<>(right.getKey(), right.getValue() + 1);
        }
        return new Pair<>(root, left.getValue() + 1);
    }
}

###C#

public class Solution {
    public TreeNode LcaDeepestLeaves(TreeNode root) {
        return f(root).Item1;
    }

    private Tuple<TreeNode, int> f(TreeNode root) {
        if (root == null) {
            return new Tuple<TreeNode, int>(root, 0);
        }

        Tuple<TreeNode, int> left = f(root.left);
        Tuple<TreeNode, int> right = f(root.right);

        if (left.Item2 > right.Item2) {
            return new Tuple<TreeNode, int>(left.Item1, left.Item2 + 1);
        }
        if (left.Item2 < right.Item2) {
            return new Tuple<TreeNode, int>(right.Item1, right.Item2 + 1);
        }
        return new Tuple<TreeNode, int>(root, left.Item2 + 1);
    }
}

###Python

class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def f(root):
            if not root:
                return 0, None

            d1, lca1 = f(root.left)
            d2, lca2 = f(root.right)

            if d1 > d2:
                return d1 + 1, lca1
            if d1 < d2:
                return d2 + 1, lca2
            return d1 + 1, root

        return f(root)[1]

###JavaScript

var lcaDeepestLeaves = function(root) {
    return f(root)[1];
};

function f(root) {
    if (!root) {
      return [0, root];
    }

    let [d1, lca1] = f(root.left);
    let [d2, lca2] = f(root.right);

    if (d1 > d2) {
      return [d1 + 1, lca1];
    }
    if (d1 < d2) {
      return [d2 + 1, lca2];
    }
    return [d1 + 1, root];
}

###Go

func lcaDeepestLeaves(root *TreeNode) *TreeNode {
    _, lca := f(root)
    return lca
}

func f(root *TreeNode) (int, *TreeNode) {
    if root == nil {
        return 0, nil
    }

    d1, lca1 := f(root.Left)
    h2, lca2 := f(root.Right)

    if d1 > h2 {
        return d1 + 1, lca1
    }
    if d1 < h2 {
        return h2 + 1, lca2
    }
    return d1 + 1, root
}

###C

struct Pair {
    struct TreeNode *node;
    int depth;
};

struct Pair f(struct TreeNode *root) {
    if (root == NULL) {
        return (struct Pair) {NULL, 0};
    }

    struct Pair left = f(root->left);
    struct Pair right = f(root->right);

    if (left.depth > right.depth) {
        return (struct Pair) {left.node, left.depth + 1};
    }
    if (left.depth < right.depth) {
        return (struct Pair) {right.node, right.depth + 1};
    }
    return (struct Pair) {root, left.depth + 1};
}

struct TreeNode *lcaDeepestLeaves(struct TreeNode *root) {
    return f(root).node;
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是树的节点数量。

• 空间复杂度：$O(d)$，其中 $d$ 是树的深度。空间复杂度主要是递归的空间，最差情况为 $O(n)$，其中 $n$ 是树的节点数量。

解题思路

第一种容想到的常规解法

类似于前序遍历，从根节点开始，分别求左右子树的高度left，和right。

• 情况1：left=right 那么两边子树的最深高度相同，返回本节点
• 情况2：left<right 说明最深节点在右子树，直接返回右子树的递归结果
• 情况2：left>right 说明最深节点在左子树，直接返回右子树的递归结果

其中求子树的高度需要定义一个方法，就是104. 二叉树的最大深度，很简单。

代码

###java

class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
       if(root==null) return null;
       int left=dfs(root.left);
       int right=dfs(root.right);
       if(left==right) return root;
       else if(left<right) return lcaDeepestLeaves(root.right);
       return lcaDeepestLeaves(root.left);
    }
    int dfs(TreeNode  node){
      if(node==null) return 0;
      return 1+Math.max(dfs(node.right),dfs(node.left));
    }
}

第二种方法，

第二种方法其实就是求后序遍历，代码结构有点类似于求最大深度，只不过要想办法保存最近的节点，和返回深度

首先定义一个点来保存最近公共祖先，定义一个pre来保存上一次得到的最近公共祖先的深度。
在递归过程中，带一个参数level表示当前遍历到的节点的深度

如果node为空，返回当前深度。
如果不为空，则当前节点的逻辑为：
分别求左子树和右子树的最大深度，left和right

• 1.left=right 如果相同，并且当前深度大于上一次的最大深度，说明当前节点为最新的最近公共祖先，上一次的没有当前这个深，将当前节点保存在结果中，并将深度pre更新。
• 2.left不等于right 则直接返左右子树的最大深度
  

class Solution {
    TreeNode res = null;
    int pre=0;
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        dfs(root,1);
        return res;

    }
    int dfs(TreeNode  node,int depth){
      if(node==null) return depth;
      int left=dfs(node.left,depth+1);
      int right =dfs(node.right,depth+1);
      if(left==right&&left>=pre){
           res=node;
           pre=left;
      } 
      return Math.max(left,right);
    }
}

方法一：贪心 + 前后缀数组

令数组 $\textit{nums}$ 的长度为 $n$。根据值公式 $(\textit{nums}[i] - \textit{nums}[j]) \times \textit{nums}[k]$ 可知，当固定 $j$ 时，$\textit{nums}[i]$ 和 $\textit{nums}[k]$ 分别取 $[0, j)$ 和 $[j + 1, n)$ 的最大值时，三元组的值最大。我们使用 $\textit{leftMax}[j]$ 和 $\textit{rightMax}[j]$ 维护前缀 $[0, j)$ 最大值和后缀 $[j + 1, n)$ 最大值，依次枚举 $j$，计算值 $(\textit{leftMax}[j] - \textit{nums}[j]) \times \textit{rightMax}[j]$，返回最大值（若所有值都为负数，则返回 $0$）。

###C++

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> leftMax(n), rightMax(n);
        for (int i = 1; i < n; i++) {
            leftMax[i] = max(leftMax[i - 1], nums[i - 1]);
            rightMax[n - 1 - i] = max(rightMax[n - i], nums[n - i]);
        }
        long long res = 0;
        for (int j = 1; j < n - 1; j++) {
            res = max(res, (long long)(leftMax[j] - nums[j]) * rightMax[j]);
        }
        return res;
    }
};

###Go

func maximumTripletValue(nums []int) int64 {
    n := len(nums)
    leftMax := make([]int, n)
    rightMax := make([]int, n)
    for i := 1; i < n; i++ {
        leftMax[i] = max(leftMax[i - 1], nums[i - 1])
    }
    for i := 1; i < n; i++ {
        rightMax[n - 1 - i] = max(rightMax[n - i], nums[n - i])
    }
    var res int64 = 0
    for j := 1; j < n - 1; j++ {
        res = max(res, int64((leftMax[j] - nums[j]) * rightMax[j]))
    }
    return res
}

###Python

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        leftMax = [0] * n
        rightMax = [0] * n
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], nums[i - 1])
            rightMax[n - 1 - i] = max(rightMax[n - i], nums[n - i])
        res = 0
        for j in range(1, n - 1):
            res = max(res, (leftMax[j] - nums[j]) * rightMax[j])
        return res

###Java

public class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], nums[i - 1]);
            rightMax[n - 1 - i] = Math.max(rightMax[n - i], nums[n - i]);
        }
        long res = 0;
        for (int j = 1; j < n - 1; j++) {
            res = Math.max(res, (long)(leftMax[j] - nums[j]) * rightMax[j]);
        }
        return res;
    }
}

###JavaScript

var maximumTripletValue = function(nums) {
    const n = nums.length;
    const leftMax = new Array(n).fill(0);
    const rightMax = new Array(n).fill(0);
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], nums[i - 1]);
        rightMax[n - 1 - i] = Math.max(rightMax[n - i], nums[n - i]);
    }
    let res = 0;
    for (let j = 1; j < n - 1; j++) {
        res = Math.max(res, (leftMax[j] - nums[j]) * rightMax[j]);
    }
    return res;
};

###TypeScript

function maximumTripletValue(nums: number[]): number {
    const n = nums.length;
    const leftMax: number[] = new Array(n).fill(0);
    const rightMax: number[] = new Array(n).fill(0);
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], nums[i - 1]);
        rightMax[n - 1 - i] = Math.max(rightMax[n - i], nums[n - i]);
    }
    let res = 0;
    for (let j = 1; j < n - 1; j++) {
        res = Math.max(res, (leftMax[j] - nums[j]) * rightMax[j]);
    }
    return res;
}

###C#

public class Solution {
    public long MaximumTripletValue(int[] nums) {
        int n = nums.Length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.Max(leftMax[i - 1], nums[i - 1]);
            rightMax[n - 1 - i] = Math.Max(rightMax[n - i], nums[n - i]);
        }
        long res = 0;
        for (int j = 1; j < n - 1; j++) {
            res = Math.Max(res, (long)(leftMax[j] - nums[j]) * rightMax[j]);
        }
        return res;
    }
}

###C

long long maximumTripletValue(int *nums, int numsSize) {
    int leftMax[numsSize], rightMax[numsSize];
    leftMax[0] = 0;
    rightMax[numsSize - 1] = 0;
    for (int i = 1; i < numsSize; i++) {
        leftMax[i] = fmax(leftMax[i - 1], nums[i - 1]);
        rightMax[numsSize - 1 - i] = fmax(rightMax[numsSize - i], nums[numsSize - i]);
    }
    long long res = 0;
    for (int j = 1; j < numsSize - 1; j++) {
        long long temp = (long long)(leftMax[j] - nums[j]) * rightMax[j];
        res = fmax(res, temp);
    }
    return res;
}

###Rust

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut left_max = vec![0; n];
        let mut right_max = vec![0; n];
        for i in 1..n {
            left_max[i] = left_max[i - 1].max(nums[i - 1]);
            right_max[n - i - 1] = right_max[n - i].max(nums[n - i]);
        }
        let mut res = 0;
        for j in 1..n - 1 {
            res = res.max((left_max[j] - nums[j]) as i64 * right_max[j] as i64);
        }
        res
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。

• 空间复杂度：$O(n)$。

方法二：贪心

类似于方法一，我们固定 $k$，那么当 $\textit{nums}[i] - \textit{nums}[j]$ 取最大值时，三元组的值最大。我们可以用 $\textit{imax}$ 维护 $\textit{nums}[i]$ 的最大值，$\textit{dmax}$ 维护 $\textit{nums}[i] - \textit{nums}[j]$ 的最大值，在枚举 $k$ 的过程中，更新 $\textit{dmax}$ 和 $\textit{imax}$。

###C++

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size();
        long long res = 0, imax = 0, dmax = 0;
        for (int k = 0; k < n; k++) {
            res = max(res, dmax * nums[k]);
            dmax = max(dmax, imax - nums[k]);
            imax = max(imax, static_cast<long long>(nums[k]));
        }
        return res;
    }
};

###Java

class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        long res = 0, imax = 0, dmax = 0;
        for (int k = 0; k < n; k++) {
            res = Math.max(res, dmax * nums[k]);
            dmax = Math.max(dmax, imax - nums[k]);
            imax = Math.max(imax, nums[k]);
        }
        return res;
    }
}

###C#

public class Solution {
    public long MaximumTripletValue(int[] nums) {
        int n = nums.Length;
        long res = 0, imax = 0, dmax = 0;
        for (int k = 0; k < n; k++) {
            res = Math.Max(res, dmax * nums[k]);
            dmax = Math.Max(dmax, imax - nums[k]);
            imax = Math.Max(imax, nums[k]);
        }
        return res;
    }
}

###Python

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        res, imax, dmax = 0, 0, 0
        for k in range(n):
            res = max(res, dmax * nums[k])
            dmax = max(dmax, imax - nums[k])
            imax = max(imax, nums[k])
        return res

###C

long long maximumTripletValue(int* nums, int numsSize) {
    long long res = 0, imax = 0, dmax = 0;
    for (int k = 0; k < numsSize; k++) {
        res = fmax(res, dmax * nums[k]);
        dmax = fmax(dmax, imax - nums[k]);
        imax = fmax(imax, nums[k]);
    }
    return res;
}

###Go

func maximumTripletValue(nums []int) int64 {
    n := len(nums)
    var res, imax, dmax int64 = 0, 0, 0
    for k := 0; k < n; k++ {
        res = max(res, dmax * int64(nums[k]))
        dmax = max(dmax, imax - int64(nums[k]))
        imax = max(imax, int64(nums[k]))
    }
    return res
}

###JavaScript

var maximumTripletValue = function(nums) {
    const n = nums.length;
    let res = 0, imax = 0, dmax = 0;
    for (let k = 0; k < n; k++) {
        res = Math.max(res, dmax * nums[k]);
        dmax = Math.max(dmax, imax - nums[k]);
        imax = Math.max(imax, nums[k]);
    }
    return res;
};

###TypeScript

function maximumTripletValue(nums: number[]): number {
    const n: number = nums.length;
    let res: number = 0, imax: number = 0, dmax: number = 0;
    for (let k = 0; k < n; k++) {
        res = Math.max(res, dmax * nums[k]);
        dmax = Math.max(dmax, imax - nums[k]);
        imax = Math.max(imax, nums[k]);
    }
    return res;
}

###Rust

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        let mut res = 0;
        let mut imax = 0;
        let mut dmax = 0;
        for &num in nums.iter() {
            res = res.max(dmax * num as i64);
            dmax = dmax.max(imax - num as i64);
            imax = imax.max(num as i64);
        }
        res
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。

• 空间复杂度：$O(1)$。

方法一：维护前缀最大值和最大差值

我们用两个变量 $\textit{mx}$ 和 $\textit{mxDiff}$ 分别维护前缀最大值和最大差值，用一个变量 $\textit{ans}$ 维护答案。初始时，这些变量都为 $0$。

接下来，我们枚举数组的每个元素 $x$ 作为 $\textit{nums}[k]$，首先更新答案 $\textit{ans} = \max(\textit{ans}, \textit{mxDiff} \times x)$，然后我们更新最大差值 $\textit{mxDiff} = \max(\textit{mxDiff}, \textit{mx} - x)$，最后更新前缀最大值 $\textit{mx} = \max(\textit{mx}, x)$。

枚举完所有元素后，返回答案 $\textit{ans}$。

###python

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        ans = mx = mx_diff = 0
        for x in nums:
            ans = max(ans, mx_diff * x)
            mx_diff = max(mx_diff, mx - x)
            mx = max(mx, x)
        return ans

###java

class Solution {
    public long maximumTripletValue(int[] nums) {
        long ans = 0, mxDiff = 0;
        int mx = 0;
        for (int x : nums) {
            ans = Math.max(ans, mxDiff * x);
            mxDiff = Math.max(mxDiff, mx - x);
            mx = Math.max(mx, x);
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        long long ans = 0, mxDiff = 0;
        int mx = 0;
        for (int x : nums) {
            ans = max(ans, mxDiff * x);
            mxDiff = max(mxDiff, 1LL * mx - x);
            mx = max(mx, x);
        }
        return ans;
    }
};

###go

func maximumTripletValue(nums []int) int64 {
ans, mx, mxDiff := 0, 0, 0
for _, x := range nums {
ans = max(ans, mxDiff*x)
mxDiff = max(mxDiff, mx-x)
mx = max(mx, x)
}
return int64(ans)
}

###ts

function maximumTripletValue(nums: number[]): number {
    let [ans, mx, mxDiff] = [0, 0, 0];
    for (const x of nums) {
        ans = Math.max(ans, mxDiff * x);
        mxDiff = Math.max(mxDiff, mx - x);
        mx = Math.max(mx, x);
    }
    return ans;
}

###rust

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        let mut ans: i64 = 0;
        let mut mx: i32 = 0;
        let mut mx_diff: i32 = 0;

        for &x in &nums {
            ans = ans.max(mx_diff as i64 * x as i64);
            mx_diff = mx_diff.max(mx - x);
            mx = mx.max(x);
        }

        ans
    }
}

时间复杂度 $O(n)$，其中 $n$ 是数组长度。空间复杂度 $O(1)$。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

示例 1：

输入：nums = [12,6,1,2,7]
输出：77
解释：下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
可以证明不存在值大于 77 的有序下标三元组。

示例 2：

输入：nums = [1,10,3,4,19]
输出：133
解释：下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以证明不存在值大于 133 的有序下标三元组。 

示例 3：

输入：nums = [1,2,3]
输出：0
解释：唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。

提示：

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 106

对于这个问题，数据范围是 $100$ 的情况，我们可以直接暴力枚举所有合法的 $(i, j, k)$ 三元组，看其值取最大即可。 注意要求如果是负值时，返回 $0$.

时间复杂度为 $\mathcal{O}(n^3)$.

具体代码如下——

###Python

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for k in range(n):
            for j in range(k):
                for i in range(j):
                    ans = max(ans, (nums[i] - nums[j]) * nums[k])
        return ans

接下来我们思考如何处理 $n \leq 10^5$ 的情况。

首先，输出的数值最小为 $0$，同时数组中每个元素均为正数，因此，我们要让 (nums[i] - nums[j]) * nums[k] 最大，只需要对于固定的 $k$ 找到其前面 nums[i] - nums[j] 的最大值。

为了使得 nums[i] - nums[j] 尽可能大，我们需要对于固定的 j 找到其前面最大的 nums[i] 再将两者相减。

以上逻辑可见代码注释。

因此我们只需要维护三个东西：到当前位置的最大值，到当前位置为止最大的 nums[i] - nums[j]，到当前位置为止最大的 (nums[i] - nums[j]) * nums[k]. 而从上面的分析可以看出，这些都可以遍历过程中实现。

因此时间复杂度是 $\mathcal{O}(n)$ 的。

具体代码如下——

###Python

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        # 当前最大值
        curr_max = 0
        # 当前最大的 nums[i] - nums[j]
        curr_v = 0
        # 当前最大的 (nums[i] - nums[j]) * nums[k]
        ans = 0
        n = len(nums)
        
        for i in range(n):
            # 答案的最大值根据最大的 nums[i] - nums[j] 和当前数值的乘积更新
            ans = max(ans, nums[i] * curr_v)
            # nums[i] - nums[j] 的最大值根据此前最大值减去当前数值更新
            curr_v = max(curr_v, curr_max - nums[i])
            # 更新前缀最大值
            curr_max = max(curr_max, nums[i])
        return ans

方法一：枚举 j

枚举 $j$，为了让 $(\textit{nums}[i] - \textit{nums}[j]) * \textit{nums}[k]$ 尽量大，我们需要知道 $j$ 左侧元素的最大值（让 $\textit{nums}[i] - \textit{nums}[j]$ 尽量大），以及 $j$ 右侧元素的最大值（让乘积尽量大）。

也就是计算 $\textit{nums}$ 的前缀最大值 $\textit{preMax}$ 和后缀最大值 $\textit{sufMax}$，这可以用递推预处理：

• $\textit{preMax}[i] = \max(\textit{preMax}[i-1], \textit{nums}[i])$
• $\textit{sufMax}[i] = \max(\textit{sufMax}[i+1], \textit{nums}[i])$

代码实现时，可以只预处理 $\textit{sufMax}$ 数组，$\textit{preMax}$ 可以在计算答案的同时算出来。

视频讲解 第二题。

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        suf_max = [0] * (n + 1)
        for i in range(n - 1, 1, -1):
            suf_max[i] = max(suf_max[i + 1], nums[i])

        ans = pre_max = 0
        for j, x in enumerate(nums):
            ans = max(ans, (pre_max - x) * suf_max[j + 1])
            pre_max = max(pre_max, x)
        return ans

class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        int[] sufMax = new int[n + 1];
        for (int i = n - 1; i > 1; i--) {
            sufMax[i] = Math.max(sufMax[i + 1], nums[i]);
        }

        long ans = 0;
        int preMax = nums[0];
        for (int j = 1; j < n - 1; j++) {
            ans = Math.max(ans, (long) (preMax - nums[j]) * sufMax[j + 1]);
            preMax = Math.max(preMax, nums[j]);
        }
        return ans;
    }
}

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> suf_max(n + 1);
        for (int i = n - 1; i > 1; i--) {
            suf_max[i] = max(suf_max[i + 1], nums[i]);
        }

        long long ans = 0;
        int pre_max = nums[0];
        for (int j = 1; j < n - 1; j++) {
            ans = max(ans, 1LL * (pre_max - nums[j]) * suf_max[j + 1]);
            pre_max = max(pre_max, nums[j]);
        }
        return ans;
    }
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))

long long maximumTripletValue(int* nums, int n) {
    int* suf_max = malloc(n * sizeof(int));
    suf_max[n - 1] = nums[n - 1];
    for (int i = n - 2; i > 1; i--) {
        suf_max[i] = MAX(suf_max[i + 1], nums[i]);
    }

    long long ans = 0;
    int pre_max = nums[0];
    for (int j = 1; j < n - 1; j++) {
        ans = MAX(ans, 1LL * (pre_max - nums[j]) * suf_max[j + 1]);
        pre_max = MAX(pre_max, nums[j]);
    }

    free(suf_max);
    return ans;
}

func maximumTripletValue(nums []int) int64 {
    ans := 0
    n := len(nums)
    sufMax := make([]int, n+1)
    for i := n - 1; i > 1; i-- {
        sufMax[i] = max(sufMax[i+1], nums[i])
    }

    preMax := 0
    for j, x := range nums {
        ans = max(ans, (preMax-x)*sufMax[j+1])
        preMax = max(preMax, x)
    }
    return int64(ans)
}

var maximumTripletValue = function(nums) {
    let n = nums.length;
    let sufMax = Array(n);
    sufMax[n - 1] = nums[n - 1];
    for (let i = n - 2; i > 1; i--) {
        sufMax[i] = Math.max(sufMax[i + 1], nums[i]);
    }

    let ans = 0;
    let preMax = nums[0];
    for (let j = 1; j < n - 1; j++) {
        ans = Math.max(ans, (preMax - nums[j]) * sufMax[j + 1]);
        preMax = Math.max(preMax, nums[j]);
    }
    return ans;
};

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut suf_max = vec![0; n + 1];
        for i in (2..n).rev() {
            suf_max[i] = suf_max[i + 1].max(nums[i]);
        }

        let mut ans = 0;
        let mut pre_max = nums[0];
        for j in 1..n - 1 {
            ans = ans.max((pre_max - nums[j]) as i64 * suf_max[j + 1] as i64);
            pre_max = pre_max.max(nums[j]);
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 为 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

方法二：枚举 k

枚举 $k$，我们需要知道 $k$ 左边 $\textit{nums}[i] - \textit{nums}[j]$ 的最大值。

类似 121. 买卖股票的最佳时机，为了计算 $\textit{nums}[i] - \textit{nums}[j]$ 的最大值，我们需要知道 $j$ 左边的 $\textit{nums}[i]$ 的最大值。

因此，在遍历的过程中：

• 维护 $\textit{nums}[i]$ 的最大值 $\textit{preMax}$。
• 维护 $\textit{preMax} - \textit{nums}[j]$ 的最大值 $\textit{maxDiff}$。
• 计算 $\textit{maxDiff} \cdot \textit{nums}[k]$，更新答案的最大值。

代码实现时，要先更新 $\textit{ans}$，再更新 $\textit{maxDiff}$，最后更新 $\textit{preMax}$。为什么？

这个顺序是精心设置的：

• 首先更新 $\textit{ans}$，此时 $\textit{maxDiff}$ 还没有更新，表示在当前元素左边的两个数的最大差值。
• 然后更新 $\textit{maxDiff}$，此时 $\textit{preMax}$ 还没有更新，表示在当前元素左边的最大值。
• 最后更新 $\textit{preMax}$。

能否修改更新顺序？

$\textit{ans}$ 依赖 $\textit{maxDiff}$，$\textit{maxDiff}$ 依赖 $\textit{preMax}$。如果修改更新顺序，那么 $\textit{maxDiff}$ 或者 $\textit{preMax}$ 会包含当前元素，就不是左边元素的计算结果了，这违反了题目 $i<j<k$ 的规定。

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        ans = max_diff = pre_max = 0
        for x in nums:
            ans = max(ans, max_diff * x)
            max_diff = max(max_diff, pre_max - x)
            pre_max = max(pre_max, x)
        return ans

class Solution {
    public long maximumTripletValue(int[] nums) {
        long ans = 0;
        int maxDiff = 0;
        int preMax = 0;
        for (int x : nums) {
            ans = Math.max(ans, (long) maxDiff * x);
            maxDiff = Math.max(maxDiff, preMax - x);
            preMax = Math.max(preMax, x);
        }
        return ans;
    }
}

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        long long ans = 0;
        int max_diff = 0, pre_max = 0;
        for (int x : nums) {
            ans = max(ans, 1LL * max_diff * x);
            max_diff = max(max_diff, pre_max - x);
            pre_max = max(pre_max, x);
        }
        return ans;
    }
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))

long long maximumTripletValue(int* nums, int n) {
    long long ans = 0;
    int max_diff = 0, pre_max = 0;
    for (int i = 0; i < n; i++) {
        ans = MAX(ans, 1LL * max_diff * nums[i]);
        max_diff = MAX(max_diff, pre_max - nums[i]);
        pre_max = MAX(pre_max, nums[i]);
    }
    return ans;
}

func maximumTripletValue(nums []int) int64 {
    var ans, maxDiff, preMax int
    for _, x := range nums {
        ans = max(ans, maxDiff*x)
        maxDiff = max(maxDiff, preMax-x)
        preMax = max(preMax, x)
    }
    return int64(ans)
}

var maximumTripletValue = function(nums) {
    let ans = 0, maxDiff = 0, preMax = 0;
    for (const x of nums) {
        ans = Math.max(ans, maxDiff * x);
        maxDiff = Math.max(maxDiff, preMax - x);
        preMax = Math.max(preMax, x);
    }
    return ans;
};

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        let mut ans = 0;
        let mut max_diff = 0;
        let mut pre_max = 0;
        for x in nums {
            ans = ans.max(max_diff as i64 * x as i64);
            max_diff = max_diff.max(pre_max - x);
            pre_max = pre_max.max(x);
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 为 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

思考题

如果 $\textit{nums}$ 中有负数，要怎么做？

欢迎在评论区分享你的思路/代码。

更多相似题目，见下面数据结构题单中的「§0.1 枚举右，维护左」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 【本题相关】常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

方法一：维护前缀最大值和最大差值

我们用两个变量 $\textit{mx}$ 和 $\textit{mxDiff}$ 分别维护前缀最大值和最大差值，用一个变量 $\textit{ans}$ 维护答案。初始时，这些变量都为 $0$。

接下来，我们枚举数组的每个元素 $x$ 作为 $\textit{nums}[k]$，首先更新答案 $\textit{ans} = \max(\textit{ans}, \textit{mxDiff} \times x)$，然后我们更新最大差值 $\textit{mxDiff} = \max(\textit{mxDiff}, \textit{mx} - x)$，最后更新前缀最大值 $\textit{mx} = \max(\textit{mx}, x)$。

枚举完所有元素后，返回答案 $\textit{ans}$。

###python

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        ans = mx = mx_diff = 0
        for x in nums:
            ans = max(ans, mx_diff * x)
            mx_diff = max(mx_diff, mx - x)
            mx = max(mx, x)
        return ans

###java

class Solution {
    public long maximumTripletValue(int[] nums) {
        long ans = 0, mxDiff = 0;
        int mx = 0;
        for (int x : nums) {
            ans = Math.max(ans, mxDiff * x);
            mxDiff = Math.max(mxDiff, mx - x);
            mx = Math.max(mx, x);
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        long long ans = 0, mxDiff = 0;
        int mx = 0;
        for (int x : nums) {
            ans = max(ans, mxDiff * x);
            mxDiff = max(mxDiff, 1LL * mx - x);
            mx = max(mx, x);
        }
        return ans;
    }
};

###go

func maximumTripletValue(nums []int) int64 {
ans, mx, mxDiff := 0, 0, 0
for _, x := range nums {
ans = max(ans, mxDiff*x)
mxDiff = max(mxDiff, mx-x)
mx = max(mx, x)
}
return int64(ans)
}

###ts

function maximumTripletValue(nums: number[]): number {
    let [ans, mx, mxDiff] = [0, 0, 0];
    for (const x of nums) {
        ans = Math.max(ans, mxDiff * x);
        mxDiff = Math.max(mxDiff, mx - x);
        mx = Math.max(mx, x);
    }
    return ans;
}

###rust

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        let mut ans: i64 = 0;
        let mut mx: i32 = 0;
        let mut mx_diff: i32 = 0;

        for &x in &nums {
            ans = ans.max(mx_diff as i64 * x as i64);
            mx_diff = mx_diff.max(mx - x);
            mx = mx.max(x);
        }

        ans
    }
}

时间复杂度 $O(n)$，其中 $n$ 是数组长度。空间复杂度 $O(1)$。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

方法一：暴力枚举

枚举所有满足 $i \lt j \lt k$ 的三元组 $(i, j, k)$，返回所有值大于等于 $0$ 的三元组的最大值。

###C++

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size();
        long long res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    res = max(res, (long long)(nums[i] - nums[j]) * nums[k]);
                }
            }
        }
        return res;
    }
};

###Go

func maximumTripletValue(nums []int) int64 {
    n := len(nums)
    var res int64 = 0
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            for k := j + 1; k < n; k++ {
                res = max(res, int64(nums[i] - nums[j]) * int64(nums[k]))
            }
        }
    }
    return res
}

###Python

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    res = max(res, (nums[i] - nums[j]) * nums[k])
        return res

###Java

class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        long res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    res = Math.max(res, (long) (nums[i] - nums[j]) * nums[k]);
                }
            }
        }
        return res;
    }
}

###JavaScript

var maximumTripletValue = function(nums) {
    let n = nums.length;
    let res = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            for (let k = j + 1; k < n; k++) {
                res = Math.max(res, (nums[i] - nums[j]) * nums[k]);
            }
        }
    }
    return res;
};

###TypeScript

function maximumTripletValue(nums: number[]): number {
    const n = nums.length;
    let res = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            for (let k = j + 1; k < n; k++) {
                res = Math.max(res, (nums[i] - nums[j]) * nums[k]);
            }
        }
    }
    return res;
}

###C#

public class Solution {
    public long MaximumTripletValue(int[] nums) {
        int n = nums.Length;
        long res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    res = Math.Max(res, (long)(nums[i] - nums[j]) * nums[k]);
                }
            }
        }
        return res;
    }
}

###C

long long maximumTripletValue(int* nums, int numsSize) {
    long long res = 0;
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            for (int k = j + 1; k < numsSize; k++) {
                long long value = (long long)(nums[i] - nums[j]) * nums[k];
                if (value > res) {
                    res = value;
                }
            }
        }
    }
    return res;
}

###Rust

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut res = 0;
        for i in 0..n {
            for j in i+1..n {
                for k in j+1..n {
                    res = res.max((nums[i] - nums[j]) as i64 * nums[k] as i64);
                }
            }
        }
        res
    }
}

复杂度分析

• 时间复杂度：$O(n^3)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。

• 空间复杂度：$O(1)$。

方法二：贪心

固定三元组 $(i, j, k)$ 的 $j$ 和 $k$ 时，由值公式 $(\textit{nums}[i] - \textit{nums}[j]) \times \textit{nums}[k]$ 可知，$\textit{nums}[i]$ 取区间 $[0, j)$ 内的最大值时，$(\textit{nums}[i] - \textit{nums}[j]) \times \textit{nums}[k]$ 最大。使用两层循环分别枚举 $k$ 和 $j$，同时使用 $m$ 维护 $[0, j)$ 的最大值，返回所有 $(m - \textit{nums}[j]) \times \textit{nums}[k]$ 的最大值（若所有值都为负数，则返回 $0$）。

###C++

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size();
        long long res = 0;
        for (int k = 2; k < n; k++) {
            int m = nums[0];
            for (int j = 1; j < k; j++) {
                res = max(res, (long long)(m - nums[j]) * nums[k]);
                m = max(m, nums[j]);
            }
        }
        return res;
    }
};

###Go

func maximumTripletValue(nums []int) int64 {
    n := len(nums)
    var res int64 = 0
    for k := 2; k < n; k++ {
        m := nums[0]
        for j := 1; j < k; j++ {
            res = max(res, int64(m - nums[j]) * int64(nums[k]))
            m = max(m, nums[j])
        }
    }
    return res
}

###Python

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        for k in range(2, n):
            m = nums[0]
            for j in range(1, k):
                res = max(res, (m - nums[j]) * nums[k])
                m = max(m, nums[j])
        return res

###Java

class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        long res = 0;
        for (int k = 2; k < n; k++) {
            int m = nums[0];
            for (int j = 1; j < k; j++) {
                res = Math.max(res, (long)(m - nums[j]) * nums[k]);
                m = Math.max(m, nums[j]);
            }
        }
        return res;
    }
}

###JavaScript

var maximumTripletValue = function(nums) {
    let n = nums.length;
    let res = 0;
    for (let k = 2; k < n; k++) {
        let m = nums[0];
        for (let j = 1; j < k; j++) {
            res = Math.max(res, (m - nums[j]) * nums[k]);
            m = Math.max(m, nums[j]);
        }
    }
    return res;
};

###TypeScript

function maximumTripletValue(nums: number[]): number {
    const n = nums.length;
    let res = 0;
    for (let k = 2; k < n; k++) {
        let m = nums[0];
        for (let j = 1; j < k; j++) {
            res = Math.max(res, (m - nums[j]) * nums[k]);
            m = Math.max(m, nums[j]);
        }
    }
    return res;
}

###C#

public class Solution {
    public long MaximumTripletValue(int[] nums) {
        int n = nums.Length;
        long res = 0;
        for (int k = 2; k < n; k++) {
            int m = nums[0];
            for (int j = 1; j < k; j++) {
                res = Math.Max(res, (long)(m - nums[j]) * nums[k]);
                m = Math.Max(m, nums[j]);
            }
        }
        return res;
    }
}

###C

long long maximumTripletValue(int* nums, int numsSize) {
    long long res = 0;
    for (int k = 2; k < numsSize; k++) {
        int m = nums[0];
        for (int j = 1; j < k; j++) {
            long long value = (long long)(m - nums[j]) * nums[k];
            if (value > res) {
                res = value;
            }
            if (nums[j] > m) {
                m = nums[j];
            }
        }
    }
    return res;
}

###Rust

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut res = 0;
        for k in 2..n {
            let mut m = nums[0];
            for j in 1..k {
                res = res.max((m - nums[j]) as i64 * nums[k] as i64);
                m = m.max(nums[j]);
            }
        }
        res
    }
}

复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。

• 空间复杂度：$O(1)$。

方法三：贪心 + 前后缀数组

令数组 $\textit{nums}$ 的长度为 $n$。根据值公式 $(\textit{nums}[i] - \textit{nums}[j]) \times \textit{nums}[k]$ 可知，当固定 $j$ 时，$\textit{nums}[i]$ 和 $\textit{nums}[k]$ 分别取 $[0, j)$ 和 $[j + 1, n)$ 的最大值时，三元组的值最大。我们使用 $\textit{leftMax}[j]$ 和 $\textit{rightMax}[j]$ 维护前缀 $[0, j)$ 最大值和后缀 $[j + 1, n)$ 最大值，依次枚举 $j$，计算值 $(\textit{leftMax}[j] - \textit{nums}[j]) \times \textit{rightMax}[j]$，返回最大值（若所有值都为负数，则返回 $0$）。

###C++

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> leftMax(n), rightMax(n);
        for (int i = 1; i < n; i++) {
            leftMax[i] = max(leftMax[i - 1], nums[i - 1]);
            rightMax[n - 1 - i] = max(rightMax[n - i], nums[n - i]);
        }
        long long res = 0;
        for (int j = 1; j < n - 1; j++) {
            res = max(res, (long long)(leftMax[j] - nums[j]) * rightMax[j]);
        }
        return res;
    }
};

###Go

func maximumTripletValue(nums []int) int64 {
    n := len(nums)
    leftMax := make([]int, n)
    rightMax := make([]int, n)
    for i := 1; i < n; i++ {
        leftMax[i] = max(leftMax[i - 1], nums[i - 1])
    }
    for i := 1; i < n; i++ {
        rightMax[n - 1 - i] = max(rightMax[n - i], nums[n - i])
    }
    var res int64 = 0
    for j := 1; j < n - 1; j++ {
        res = max(res, int64((leftMax[j] - nums[j]) * rightMax[j]))
    }
    return res
}

###Python

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        leftMax = [0] * n
        rightMax = [0] * n
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], nums[i - 1])
            rightMax[n - 1 - i] = max(rightMax[n - i], nums[n - i])
        res = 0
        for j in range(1, n - 1):
            res = max(res, (leftMax[j] - nums[j]) * rightMax[j])
        return res

###Java

public class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], nums[i - 1]);
            rightMax[n - 1 - i] = Math.max(rightMax[n - i], nums[n - i]);
        }
        long res = 0;
        for (int j = 1; j < n - 1; j++) {
            res = Math.max(res, (long)(leftMax[j] - nums[j]) * rightMax[j]);
        }
        return res;
    }
}

###JavaScript

var maximumTripletValue = function(nums) {
    const n = nums.length;
    const leftMax = new Array(n).fill(0);
    const rightMax = new Array(n).fill(0);
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], nums[i - 1]);
        rightMax[n - 1 - i] = Math.max(rightMax[n - i], nums[n - i]);
    }
    let res = 0;
    for (let j = 1; j < n - 1; j++) {
        res = Math.max(res, (leftMax[j] - nums[j]) * rightMax[j]);
    }
    return res;
};

###TypeScript

function maximumTripletValue(nums: number[]): number {
    const n = nums.length;
    const leftMax: number[] = new Array(n).fill(0);
    const rightMax: number[] = new Array(n).fill(0);
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], nums[i - 1]);
        rightMax[n - 1 - i] = Math.max(rightMax[n - i], nums[n - i]);
    }
    let res = 0;
    for (let j = 1; j < n - 1; j++) {
        res = Math.max(res, (leftMax[j] - nums[j]) * rightMax[j]);
    }
    return res;
}

###C#

public class Solution {
    public long MaximumTripletValue(int[] nums) {
        int n = nums.Length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.Max(leftMax[i - 1], nums[i - 1]);
            rightMax[n - 1 - i] = Math.Max(rightMax[n - i], nums[n - i]);
        }
        long res = 0;
        for (int j = 1; j < n - 1; j++) {
            res = Math.Max(res, (long)(leftMax[j] - nums[j]) * rightMax[j]);
        }
        return res;
    }
}

###C

long long maximumTripletValue(int *nums, int numsSize) {
    int leftMax[numsSize], rightMax[numsSize];
    leftMax[0] = 0;
    rightMax[numsSize - 1] = 0;
    for (int i = 1; i < numsSize; i++) {
        leftMax[i] = fmax(leftMax[i - 1], nums[i - 1]);
        rightMax[numsSize - 1 - i] = fmax(rightMax[numsSize - i], nums[numsSize - i]);
    }
    long long res = 0;
    for (int j = 1; j < numsSize - 1; j++) {
        long long temp = (long long)(leftMax[j] - nums[j]) * rightMax[j];
        res = fmax(res, temp);
    }
    return res;
}

###Rust

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut left_max = vec![0; n];
        let mut right_max = vec![0; n];
        for i in 1..n {
            left_max[i] = left_max[i - 1].max(nums[i - 1]);
            right_max[n - i - 1] = right_max[n - i].max(nums[n - i]);
        }
        let mut res = 0;
        for j in 1..n - 1 {
            res = res.max((left_max[j] - nums[j]) as i64 * right_max[j] as i64);
        }
        res
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。

• 空间复杂度：$O(n)$。

方法四：贪心

类似于方法三，我们固定 $k$，那么当 $\textit{nums}[i] - \textit{nums}[j]$ 取最大值时，三元组的值最大。我们可以用 $\textit{imax}$ 维护 $\textit{nums}[i]$ 的最大值，$\textit{dmax}$ 维护 $\textit{nums}[i] - \textit{nums}[j]$ 的最大值，在枚举 $k$ 的过程中，更新 $\textit{dmax}$ 和 $\textit{imax}$。

###C++

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size();
        long long res = 0, imax = 0, dmax = 0;
        for (int k = 0; k < n; k++) {
            res = max(res, dmax * nums[k]);
            dmax = max(dmax, imax - nums[k]);
            imax = max(imax, static_cast<long long>(nums[k]));
        }
        return res;
    }
};

###Java

class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        long res = 0, imax = 0, dmax = 0;
        for (int k = 0; k < n; k++) {
            res = Math.max(res, dmax * nums[k]);
            dmax = Math.max(dmax, imax - nums[k]);
            imax = Math.max(imax, nums[k]);
        }
        return res;
    }
}

###C#

public class Solution {
    public long MaximumTripletValue(int[] nums) {
        int n = nums.Length;
        long res = 0, imax = 0, dmax = 0;
        for (int k = 0; k < n; k++) {
            res = Math.Max(res, dmax * nums[k]);
            dmax = Math.Max(dmax, imax - nums[k]);
            imax = Math.Max(imax, nums[k]);
        }
        return res;
    }
}

###Python

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        res, imax, dmax = 0, 0, 0
        for k in range(n):
            res = max(res, dmax * nums[k])
            dmax = max(dmax, imax - nums[k])
            imax = max(imax, nums[k])
        return res

###C

long long maximumTripletValue(int* nums, int numsSize) {
    long long res = 0, imax = 0, dmax = 0;
    for (int k = 0; k < numsSize; k++) {
        res = fmax(res, dmax * nums[k]);
        dmax = fmax(dmax, imax - nums[k]);
        imax = fmax(imax, nums[k]);
    }
    return res;
}

###Go

func maximumTripletValue(nums []int) int64 {
    n := len(nums)
    var res, imax, dmax int64 = 0, 0, 0
    for k := 0; k < n; k++ {
        res = max(res, dmax * int64(nums[k]))
        dmax = max(dmax, imax - int64(nums[k]))
        imax = max(imax, int64(nums[k]))
    }
    return res
}

###JavaScript

var maximumTripletValue = function(nums) {
    const n = nums.length;
    let res = 0, imax = 0, dmax = 0;
    for (let k = 0; k < n; k++) {
        res = Math.max(res, dmax * nums[k]);
        dmax = Math.max(dmax, imax - nums[k]);
        imax = Math.max(imax, nums[k]);
    }
    return res;
};

###TypeScript

function maximumTripletValue(nums: number[]): number {
    const n: number = nums.length;
    let res: number = 0, imax: number = 0, dmax: number = 0;
    for (let k = 0; k < n; k++) {
        res = Math.max(res, dmax * nums[k]);
        dmax = Math.max(dmax, imax - nums[k]);
        imax = Math.max(imax, nums[k]);
    }
    return res;
}

###Rust

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        let mut res = 0;
        let mut imax = 0;
        let mut dmax = 0;
        for &num in nums.iter() {
            res = res.max(dmax * num as i64);
            dmax = dmax.max(imax - num as i64);
            imax = imax.max(num as i64);
        }
        res
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。

• 空间复杂度：$O(1)$。

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

示例 1：

输入：nums = [12,6,1,2,7]
输出：77
解释：下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
可以证明不存在值大于 77 的有序下标三元组。

示例 2：

输入：nums = [1,10,3,4,19]
输出：133
解释：下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以证明不存在值大于 133 的有序下标三元组。 

示例 3：

输入：nums = [1,2,3]
输出：0
解释：唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。

提示：

• 3 <= nums.length <= 100
• 1 <= nums[i] <= 106

解法一

思路和算法

直观的思路是遍历每个下标三元组 $(i, j, k)$ 计算 $(\textit{nums}[i] - \textit{nums}[j]) \times \textit{nums}[k]$ 的值，并得到最大值。

用 $\textit{maxValue}$ 表示下标三元组的最大值，初始时 $\textit{maxValue} = 0$，遍历过程中如果遇到一个下标三元组的值大于 $\textit{maxValue}$，则用该下标三元组的值更新 $\textit{maxValue}$。遍历结束之后，$\textit{maxValue}$ 即为下标三元组的最大值。

根据题目要求，如果所有下标三元组的值都是负数则返回 $0$。由于 $\textit{maxValue}$ 的初始值是 $0$，因此如果所有下标三元组的值都是负数，则 $\textit{maxValue}$ 的值不会更新，符合题目要求。

代码

###Java

class Solution {
    public long maximumTripletValue(int[] nums) {
        long maxValue = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    long value = (long) (nums[i] - nums[j]) * nums[k];
                    maxValue = Math.max(maxValue, value);
                }
            }
        }
        return maxValue;
    }
}

###C#

public class Solution {
    public long MaximumTripletValue(int[] nums) {
        long maxValue = 0;
        int n = nums.Length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    long value = (long) (nums[i] - nums[j]) * nums[k];
                    maxValue = Math.Max(maxValue, value);
                }
            }
        }
        return maxValue;
    }
}

复杂度分析

• 时间复杂度：$O(n^3)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。需要使用三层循环遍历所有的下标三元组并计算值。

• 空间复杂度：$O(1)$。

解法二

思路和算法

下标三元组 $(i, j, k)$ 满足 $i < j < k$。当下标 $j$ 确定时，为了使下标三元组的值最大，应使 $\textit{nums}[i]$ 和 $\textit{nums}[k]$ 最大。用 $n$ 表示数组 $\textit{nums}$ 的长度，则 $1 \le j \le n - 2$，当下标 $j$ 确定时，$\textit{nums}[i]$ 应取数组 $\textit{nums}$ 的下标范围 $[0, j - 1]$ 中的最大值，$\textit{nums}[k]$ 应取数组 $\textit{nums}$ 的下标范围 $[j + 1, n - 1]$ 中的最大值，因此需要维护数组 $\textit{nums}$ 的每个前缀与后缀的最大值。

创建长度为 $n$ 的数组 $\textit{leftMax}$ 和 $\textit{rightMax}$，其中 $\textit{leftMax}[i]$ 表示数组 $\textit{nums}$ 的下标范围 $[0, i]$ 中的最大值，$\textit{rightMax}[i]$ 表示数组 $\textit{nums}$ 的下标范围 $[i, n - 1]$ 中的最大值。数组 $\textit{leftMax}$ 和 $\textit{rightMax}$ 的元素值计算如下。

1. 当 $i = 0$ 时，$\textit{leftMax}[i] = \textit{nums}[i]$；当 $i = n - 1$ 时，$\textit{rightMax}[i] = \textit{nums}[i]$。

2. 当 $i > 0$ 时，$\textit{leftMax}[i] = \max(\textit{leftMax}[i - 1], \textit{nums}[i])$；当 $i < n - 1$ 时，$\textit{rightMax}[i] = \max(\textit{rightMax}[i + 1], \textit{nums}[i])$。

计算得到数组 $\textit{leftMax}$ 和 $\textit{rightMax}$ 的值之后，即可计算下标三元组的最大值。对于每个 $1 \le j \le n - 2$，当下标 $j$ 固定时，下标三元组 $(i, j, k)$ 的最大值是 $(\textit{leftMax}[j - 1] - \textit{nums}[j]) \times \textit{rightMax}[j + 1]$。遍历所有可能的下标 $j$ 之后即可得到下标三元组的最大值。

特别地，当所有下标三元组的值都是负数时，返回 $0$。

代码

###Java

class Solution {
    public long maximumTripletValue(int[] nums) {
        long maxValue = 0;
        int n = nums.length;
        int[] leftMax = new int[n];
        leftMax[0] = nums[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], nums[i]);
        }
        int[] rightMax = new int[n];
        rightMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
        }
        for (int j = 1; j < n - 1; j++) {
            long value = (long) (leftMax[j - 1] - nums[j]) * (rightMax[j + 1]);
            maxValue = Math.max(maxValue, value);
        }
        return maxValue;
    }
}

###C#

public class Solution {
    public long MaximumTripletValue(int[] nums) {
        long maxValue = 0;
        int n = nums.Length;
        int[] leftMax = new int[n];
        leftMax[0] = nums[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.Max(leftMax[i - 1], nums[i]);
        }
        int[] rightMax = new int[n];
        rightMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.Max(rightMax[i + 1], nums[i]);
        }
        for (int j = 1; j < n - 1; j++) {
            long value = (long) (leftMax[j - 1] - nums[j]) * (rightMax[j + 1]);
            maxValue = Math.Max(maxValue, value);
        }
        return maxValue;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。计算前缀最大值数组与后缀最大值数组的时间是 $O(n)$，计算三元组最大值的时间是 $O(n)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。需要创建两个长度为 $n$ 的数组。

解法三

思路和算法

下标三元组 $(i, j, k)$ 满足 $i < j < k$。可以从左到右遍历数组 $\textit{nums}$，对于每个下标 $k$ 计算 $\textit{nums}[i] - \textit{nums}[j]$ 的最大值，得到下标 $k$ 确定时的下标三元组的最大值。

遍历过程中需要维护已经遍历过的元素的最大差值 $\textit{maxDiff}$ 和最大元素值 $\textit{maxNum}$，初始时 $\textit{maxDiff} = \textit{maxNum} = 0$。当遍历到元素 $\textit{num}$ 时，执行如下操作。

1. 将当前元素之前的最大差值 $\textit{maxDiff}$ 作为 $\textit{nums}[i] - \textit{nums}[j]$ 的最大值，将当前元素 $\textit{num}$ 作为 $\textit{nums}[k]$，计算下标三元组的值 $\textit{maxDiff} \times \textit{num}$，使用该下标三元组的值更新结果。

2. 计算当前元素之前的最大元素值与当前元素值之差 $\textit{maxNum} - \textit{num}$，并更新 $\textit{maxDiff}$ 的值。

3. 使用当前元素值更新最大元素值 $\textit{maxNum}$。

上述操作中，每次计算下标三元组的值时，$\textit{maxDiff}$ 一定是当前元素之前的两个元素 $\textit{nums}[i]$ 与 $\textit{nums}[j]$ 之差且一定有 $i < j$，因此可以确保得到正确的结果。

代码

###Java

class Solution {
    public long maximumTripletValue(int[] nums) {
        long maxValue = 0;
        int maxDiff = 0;
        int maxNum = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            maxValue = Math.max(maxValue, (long) maxDiff * num);
            maxDiff = Math.max(maxDiff, maxNum - num);
            maxNum = Math.max(maxNum, num);
        }
        return maxValue;
    }
}

###C#

public class Solution {
    public long MaximumTripletValue(int[] nums) {
        long maxValue = 0;
        int maxDiff = 0;
        int maxNum = 0;
        int n = nums.Length;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            maxValue = Math.Max(maxValue, (long) maxDiff * num);
            maxDiff = Math.Max(maxDiff, maxNum - num);
            maxNum = Math.Max(maxNum, num);
        }
        return maxValue;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。需要遍历数组一次。

• 空间复杂度：$O(1)$。

前缀后缀最大，时间复杂度O(n)，空间复杂度O(n)

###cpp

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size();
        
        // 记录每个元素左边最大和右边最大
        vector<pair<long long, long long>> vec(n);
        
        int left = 0, right = 0;
        for (int i = n - 1; i >= 0; --i) {
            vec[i].second = right;
            right = std::max(nums[i], right);
        }
        
        for (int i = 0; i < n; ++i) {
            vec[i].first = left;
            left = std::max(nums[i], left);
        }
        
        long long res = 0;
        for (int i = 0; i < n; ++i) {
            long long num = (vec[i].first - nums[i]) * (vec[i].second);
            if (res < num) res = num;
        }
        return res;
    }
};

本题和 2874. 有序三元组中的最大值 II 是一样的，请看 我的题解。

这里首先复述下官解方法1的做法。用dp[i]来表示枚举到第i个题目时，可以获得的最大分数。

• 如果不选第i个题，有dp[i]=dp[i−1]
• 如果选第i个题，需要遍历j$\in$[0, i-1]，找到满足j + brainpower[j] < i的值最大的dp[j]，从其转移而来，有dp[i] = dp[j] + points[i]

最终dp[i]的结果则为dp[i] = max(dp[i - 1], dp[j] + points[i])，代码实现如下：

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)
        dp = [0] * n
        dp[0] = questions[0][0]
        for i in range(1, n):
            not_select = dp[i - 1]  # 不解决
            select = questions[i][0]  # 解决
            plus = 0  # 如果从上一个已解决的题转化而来，可获得的额外分数
            for j in range(0, i):
                if j + questions[j][1] < i:
                    plus = max(plus, dp[j])
            dp[i] = max(not_select, select + plus)
        return dp[n - 1]

而以上解法是错误的(并非溢出问题)，只能通过一半的用例，一个较短的错误用例如下：

[[21,2],[1,2],[12,5],[7,2],[35,3],[32,2],[80,2],[91,5],[92,3],[27,3],[19,1],[37,3],[85,2],[33,4],[25,1],[91,4],[44,3],[93,3],[65,4],[82,3],[85,5],[81,3],[29,2],[25,1],[74,2],[58,1],[85,1],[84,2],[27,2],[47,5],[48,4],[3,2],[44,3],[60,5],[19,2],[9,4],[29,5],[15,3],[1,3],[60,2],[63,3],[79,3],[19,1],[7,1],[35,1],[55,4],[1,4],[41,1],[58,5]]

预计输出为：

781

实际输出为：

805

可以发现实际输出更大了，也就是多贪心了状态。那么问题出在哪呢？

这里举一个更简单的例子：

[[100,5],[1,1],[1,2],[1,1]]

预计输出应为100，也就是只选第0个问题回答，而以上代码的输出为101。将此时的代码的dp数组输出，有：

[100, 100, 100, 101]

其计算逻辑为：

dp[0] = points[0] = 100
dp[1] = dp[0] = 100
dp[2] = dp[1] = 100
dp[3] = dp[1] + points[3] = 101 (因为dp[1]的brainpower[i]为1，与答第2题冲突，但与答第3题不冲突)

可以发现，问题出在dp[1]上。因为dp[1]是由dp[0]转移而来，隐式的选择了dp[0]，因此其实际的"脑力恢复期"为max(0 + brainpower[0], 1 + brainbrainpower[1]) = 5，而非1 + brainbrainpower[1] = 2。也就是说，判断dp[j]是否能由dp[i]转化而来，不能只依靠：

if j + questions[j][1] < i:
    plus = max(plus, dp[j])

因为当遍历到第j个元素时，某个小于j的已选元素k的"脑力恢复期"可能仍未结束，因此不能只考虑选择j所造成的"脑力恢复期"。

给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。

这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得  pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。

• 比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：
  • 如果问题 0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2 。
  • 如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。

请你返回这场考试里你能获得的 最高 分数。

示例 1：

输入：questions = [[3,2],[4,3],[4,4],[2,5]]
输出：5
解释：解决问题 0 和 3 得到最高分。
- 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。
- 不能解决问题 1 和 2
- 解决问题 3 ：获得 2 分
总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。

示例 2：

输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出：7
解释：解决问题 1 和 4 得到最高分。
- 跳过问题 0
- 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。
- 不能解决问题 2 和 3
- 解决问题 4 ：获得 5 分
总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。

提示：

• 1 <= questions.length <= 105
• questions[i].length == 2
• 1 <= pointsi, brainpoweri <= 105

方法一：动态规划

提示 $1$

我们可以尝试用 $\textit{dp}[i]$ 来表示解决前 $i$ 道题目可以获得的最高分数。根据是否选择解决第 $i$ 道题目，会有以下两种情况：

• 不解决第 $i$ 道题目，此时 $\textit{dp}[i] = \textit{dp}[i-1]$；
• 解决第 $i$ 道题目，此时要么前面的题目都未解决，要么上一道解决的题目对应的冷冻期已经结束。具体而言：

$$
\textit{dp}[i] = \textit{points}[i] + \max(0, \max_{j \in [0, i - 1], j + \textit{brainpower}[j] < i} dp[j]).
$$

由于每一道题对应的冷冻期都不一样，因此我们很难在不通过遍历 $[0, i - 1]$ 闭区间内的全部下标，以判断对应的冷冻期是否结束的情况下更新 $\textit{dp}[i]$。我们假设题目的总数为 $n$，这样的时间复杂度为 $O(n^2)$，不符合题目要求。

提示 $2$

我们可以从无后效性的角度考虑动态规划「状态」的定义。对于每一道题目，解决与否会影响到后面一定数量题目的结果，但不会影响到前面题目的解决。因此我们可以考虑从反方向定义「状态」，即考虑解决每道题本身及以后的题目可以获得的最高分数。

思路与算法

根据提示 $2$，我们用 $\textit{dp}[i]$ 来表示解决第 $i$ 道题目及以后的题目可以获得的最高分数。同时，我们从后往前遍历题目，并更新 $\textit{dp}$ 数组。类似地，根据是否选择解决第 $i$ 道题目，会有以下两种情况：

• 不解决第 $i$ 道题目，此时 $\textit{dp}[i] = \textit{dp}[i+1]$；
• 解决第 $i$ 道题目，我们只能解决下标大于 $i + \textit{brainpower}[i]$ 的题目，而此时根据 $\textit{dp}$ 数组的定义，解决这些题目的最高分数为 $dp[i + \textit{brainpower}[i] + 1]$（当 $i \ge n$ 的情况下，我们认为 $dp[i] = 0$）。因此，我们有：

$$
\textit{dp}[i] = \textit{points}[i] + dp[i + \textit{brainpower}[i] + 1].
$$

综合上述两种情况，我们就得出了 $\textit{dp}[i]$ 的状态转移方程：

$$
\textit{dp}[i] = \max(\textit{dp}[i+1], \textit{points}[i] + dp[i + \textit{brainpower}[i] + 1]).
$$

在实际计算中，考虑到 $i \ge n$ 的边界条件，我们在定义 $\textit{dp}$ 数组时，可以预留 $dp[n] = 0$ 用来表示没有做任何题目的分数。那么上面的转移方程变为：

$$
\textit{dp}[i] = \max(\textit{dp}[i+1], \textit{points}[i] + dp[\min(n, i + \textit{brainpower}[i] + 1)]).
$$

最终，$dp[0]$ 即为考试中可以获得的最高分数，我们返回该数值作为答案。

细节

在计算 $\textit{dp}$ 数组时，数组元素的大小有可能超过 $32$ 为有符号整数的上界，因此对于 $\texttt{C++}$ 等语言，我们需要用 $64$ 位整数来存储 $\textit{dp}$ 数组。

代码

###C++

class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions) {
        int n = questions.size();
        vector<long long> dp(n + 1);   // 解决每道题及以后题目的最高分数
        for (int i = n - 1; i >= 0; --i) {
            dp[i] = max(dp[i + 1], questions[i][0] + dp[min(n, i + questions[i][1] + 1)]);
        }
        return dp[0];
    }
};

###Python

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)
        dp = [0] * (n + 1)  # 解决每道题及以后题目的最高分数
        for i in range(n - 1, -1, -1):
            dp[i] = max(
                dp[i + 1], questions[i][0] + dp[min(n, i + questions[i][1] + 1)]
            )
        return dp[0]

###Java

class Solution {
    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[n + 1]; // 解决每道题及以后题目的最高分数
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = Math.max(dp[i + 1], questions[i][0] + dp[Math.min(n, i + questions[i][1] + 1)]);
        }
        return dp[0];
    }
}

###C#

public class Solution {
    public long MostPoints(int[][] questions) {
        int n = questions.Length;
        long[] dp = new long[n + 1]; // 解决每道题及以后题目的最高分数
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = Math.Max(dp[i + 1], questions[i][0] + dp[Math.Min(n, i + questions[i][1] + 1)]);
        }
        return dp[0];
    }
}

###Go

func mostPoints(questions [][]int) int64 {
    n := len(questions)
    dp := make([]int64, n + 1) // 解决每道题及以后题目的最高分数
    for i := n - 1; i >= 0; i-- {
        dp[i] = max(dp[i + 1], int64(questions[i][0]) + dp[min(n, i + questions[i][1] + 1)])
    }
    return dp[0]
}

###C

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

long long min(long long a, long long b) {
    return a < b ? a : b;
}

long long mostPoints(int** questions, int questionsSize, int* questionsColSize) {
    long long dp[questionsSize + 1]; // 解决每道题及以后题目的最高分数
    memset(dp, 0, sizeof(dp));
    for (int i = questionsSize - 1; i >= 0; --i) {
        dp[i] = max(dp[i + 1], questions[i][0] + dp[min(questionsSize, i + questions[i][1] + 1)]);
    }
    long long result = dp[0];
    return result;
}

###JavaScript

var mostPoints = function(questions) {
    const n = questions.length;
    const dp = new Array(n + 1).fill(0); // 解决每道题及以后题目的最高分数
    for (let i = n - 1; i >= 0; i--) {
        dp[i] = Math.max(dp[i + 1], questions[i][0] + dp[Math.min(n, i + questions[i][1] + 1)]);
    }
    return dp[0];
};

###JavaScript

function mostPoints(questions: number[][]): number {
    const n = questions.length;
    const dp: number[] = new Array(n + 1).fill(0); // 解决每道题及以后题目的最高分数
    for (let i = n - 1; i >= 0; i--) {
        dp[i] = Math.max(dp[i + 1], questions[i][0] + dp[Math.min(n, i + questions[i][1] + 1)]);
    }
    return dp[0];
};

###Rust

impl Solution {
    pub fn most_points(questions: Vec<Vec<i32>>) -> i64 {
        let n = questions.len();
        let mut dp = vec![0i64; n + 1]; // 解决每道题及以后题目的最高分数
        for i in (0..n).rev() {
            dp[i] = dp[i + 1].max(questions[i][0] as i64 + dp[(n).min(i + questions[i][1] as usize + 1)]);
        }
        dp[0]
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为 $\textit{questions}$ 数组的长度。即为动态规划计算可以获得的最高分数的时间复杂度。

• 空间复杂度：$O(n)$，即为动态规划数组的空间开销。