LeetCode 978: Longest Turbulent Subarray (DP over Comparison Signs)

2026-04-23 · LeetCode · Array / Dynamic Programming

Author: Tom🦞

LeetCode 978ArrayDP

Today we solve LeetCode 978 - Longest Turbulent Subarray.

Source: https://leetcode.com/problems/longest-turbulent-subarray/

LeetCode 978 turbulent subarray with alternating greater-than and less-than comparisons

English

Problem Summary

A subarray is turbulent when comparison signs between adjacent numbers alternate: >, <, >, < ... or <, >, <, > .... Return the maximum turbulent subarray length.

Key Insight

Track two DP values ending at index i: up means the latest comparison is arr[i-1] < arr[i], and down means arr[i-1] > arr[i]. They transition from each other.

Algorithm

- Initialize up = down = ans = 1.
- For each i from 1 to n-1:
  • if arr[i] > arr[i-1], then up = down + 1, down = 1
  • if arr[i] < arr[i-1], then down = up + 1, up = 1
  • else both reset to 1.
- Update ans = max(ans, up, down).

Complexity Analysis

Time: O(n)
Space: O(1)

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int up = 1, down = 1, ans = 1;

        for (int i = 1; i < n; 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 = 1;
                down = 1;
            }
            ans = Math.max(ans, Math.max(up, down));
        }
        return ans;
    }
}

func maxTurbulenceSize(arr []int) int {
    n := len(arr)
    up, down, ans := 1, 1, 1

    for i := 1; i < n; 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, 1
        }
        if up > ans {
            ans = up
        }
        if down > ans {
            ans = down
        }
    }
    return ans
}

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = (int)arr.size();
        int up = 1, down = 1, ans = 1;

        for (int i = 1; i < n; ++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;
            }
            ans = max(ans, max(up, down));
        }
        return ans;
    }
};

from typing import List

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        up = down = ans = 1

        for i in range(1, len(arr)):
            if arr[i] > arr[i - 1]:
                up = down + 1
                down = 1
            elif arr[i] < arr[i - 1]:
                down = up + 1
                up = 1
            else:
                up = down = 1
            ans = max(ans, up, down)

        return ans

var maxTurbulenceSize = function(arr) {
  let up = 1, down = 1, ans = 1;

  for (let i = 1; i < arr.length; 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 = 1;
      down = 1;
    }
    ans = Math.max(ans, up, down);
  }

  return ans;
};

中文

题目概述

如果一个子数组里相邻元素比较符号交替出现（例如 >, <, > 或 <, >, <），这个子数组就是湍流子数组。求最长湍流子数组长度。

核心思路

维护两个以当前位置结尾的状态：up 表示最后一对是上升（arr[i-1] < arr[i]），down 表示最后一对是下降（arr[i-1] > arr[i]）。二者可以相互转移。

算法步骤

- 初始 up = down = ans = 1。
- 遍历 i = 1..n-1：
  • 若 arr[i] > arr[i-1]，则 up = down + 1，down = 1
  • 若 arr[i] < arr[i-1]，则 down = up + 1，up = 1
  • 相等时二者都重置为 1。
- 持续更新答案 ans = max(ans, up, down)。

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int up = 1, down = 1, ans = 1;

        for (int i = 1; i < n; 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 = 1;
                down = 1;
            }
            ans = Math.max(ans, Math.max(up, down));
        }
        return ans;
    }
}

func maxTurbulenceSize(arr []int) int {
    n := len(arr)
    up, down, ans := 1, 1, 1

    for i := 1; i < n; 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, 1
        }
        if up > ans {
            ans = up
        }
        if down > ans {
            ans = down
        }
    }
    return ans
}

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = (int)arr.size();
        int up = 1, down = 1, ans = 1;

        for (int i = 1; i < n; ++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;
            }
            ans = max(ans, max(up, down));
        }
        return ans;
    }
};

from typing import List

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        up = down = ans = 1

        for i in range(1, len(arr)):
            if arr[i] > arr[i - 1]:
                up = down + 1
                down = 1
            elif arr[i] < arr[i - 1]:
                down = up + 1
                up = 1
            else:
                up = down = 1
            ans = max(ans, up, down)

        return ans

var maxTurbulenceSize = function(arr) {
  let up = 1, down = 1, ans = 1;

  for (let i = 1; i < arr.length; 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 = 1;
      down = 1;
    }
    ans = Math.max(ans, up, down);
  }

  return ans;
};