求最大子数组之和

Question

这是在OA中询问的。给定一个大小为

n

的正整数数组。

从

0 to n

循环，对于数组中的每个项目，选择当前项目可能的最大子数组并将子数组大小添加到结果

示例：

arr = [3,5,6]
Result = 6

说明：

i=0 => [3] = max subarray with 3 as maximum, size of sub-array is 1

i=1 => [3,5] = max subarray with 5 as maximum, size of sub-array is 2

i=2 => [6] = max subarray with 6 as maximum, size of sub-array is 3

Sum  = 1 + 2 + 3 = 6

示例：

arr = [ 1,2,1]
Result = 5

说明：

i = 0 => [1] max subarray, size = 1
i = 1 => [1, 2, 1] max subarray with 2 as maximum, size = 3
i = 2 => [1], max subarray with 1 as maximum, size = 1

Result = 1 + 3 + 1 = 5

示例：

arr = [1,1,1,1]
Result = 16

说明：

i = 0 => [1, 1, 1, 1] max subarray with 1 as maximum, size = 4
Same for i=1, 2, 3 => max subarray for each case is still [1,1,1,1] with size 4
Result = 4 + 4 + 4 + 4 = 16

这是我的代码：

public class Main {

  public static int solve(int[] arr) {
    int n = arr.length;
    int result = 0;
    int currentMax = Integer.MIN_VALUE;

    int size = 0;
    for (int i = 0; i < n; i++) {
      currentMax = Math.max(currentMax, arr[i]);
          
      if (arr[i] == currentMax) {
          size++;
          int backUp = size;
          for(int j=i+1; j<n; j++) {
              if(arr[j] <= currentMax) {
                  size++;
              } else {
                  break;
              }
          }
        result += size;
        size = backUp;
      } else {
          size = 1;
          currentMax = arr[i];
          result++;
      }
    }

    return result;
  }

  public static void main(String[] args) {
    System.out.println(solve(new int[]{3,5,6}));//6
    System.out.println(solve(new int[]{1,2,1}));//5
    System.out.println(solve(new int[]{1,1,1,1}));//16
  }
}

我的代码仅适用于示例测试用例，而对于隐藏的其余用例则失败，因此我看不到它们。解决这个问题的正确方法是什么，测试用例失败，说输出错误，没有超时错误。

Answer 1

这个问题本质上只需要为数组的每个元素找到两侧最接近的较大元素。这可以通过单调堆栈来完成。

public static long solve(int[] arr) {
    var dq = new ArrayDeque<Integer>(arr.length);
    int[] prevLarger = new int[arr.length], nextLarger = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        while (!dq.isEmpty() && arr[dq.peek()] <= arr[i]) dq.pop();
        prevLarger[i] = dq.isEmpty() ? -1 : dq.peek();
        dq.push(i);
    }
    dq.clear();
    for (int i = arr.length - 1; i >= 0; i--) {
        while (!dq.isEmpty() && arr[dq.peek()] <= arr[i]) dq.pop();
        nextLarger[i] = dq.isEmpty() ? arr.length : dq.peek();
        dq.push(i);
    }
    long ans = 0;
    for (int i = 0; i < arr.length; i++) ans += nextLarger[i] - prevLarger[i] - 1;
    return ans;
}