如何优化该O(N^3)复杂度的算法以降低计算复杂度并提升效率？

Hey there! Let's start by fixing a critical bug in your original code before diving into optimizations—right now, your innermost loop checks x[i] < x[i-1] repeatedly for every k from i+1 to j, which doesn't actually verify if the subarray from i to j is non-decreasing. That condition never changes as k increments, so your code isn't correctly identifying valid subarrays. The correct check should be x[k] < x[k-1] to ensure each consecutive pair in the subarray follows the non-decreasing rule.

Now, let's talk about slashing that O(N³) time complexity down to something far more efficient:

Step 1: Optimize to O(N²) Complexity #

The core waste in the original code is that it rechecks the entire subarray i to j every time j increments. Instead, we can build on the previous check incrementally:

• For each starting index i, expand j forward as long as the next element maintains the non-decreasing property.
• If x[j] >= x[j-1], the subarray i to j is still valid; if not, we can stop expanding j for this i (since any longer subarray starting at i will include this invalid pair).

Here's the revised O(N²) code:

int x[100001], n;
int maxi = 1; // At minimum, the longest subarray is length 1
for (int i = 1; i <= n; i++) {
    int current_length = 1;
    for (int j = i + 1; j <= n; j++) {
        if (x[j] >= x[j-1]) {
            current_length++;
            if (current_length > maxi) {
                maxi = current_length;
            }
        } else {
            break; // No need to check further for this starting i
        }
    }
}
cout << maxi;

Step 2: Optimize to O(N) Complexity (Optimal Solution) #

We can do even better with a single pass through the array. Instead of checking every starting index, we just track the length of the current non-decreasing subarray as we iterate:

• Initialize current_length to 1 and maxi to 1 (since a single element is always a valid subarray).
• For each element from the second one to the end:
  • If it's >= the previous element, increment current_length.
  • If not, reset current_length to 1 (we start a new subarray here).
  • Update maxi whenever current_length exceeds its current value.

This runs in linear time because we only traverse the array once—no nested loops at all. Here's the optimal code:

int x[100001], n;
int maxi = 1;
int current_length = 1;
for (int i = 2; i <= n; i++) {
    if (x[i] >= x[i-1]) {
        current_length++;
        if (current_length > maxi) {
            maxi = current_length;
        }
    } else {
        current_length = 1;
    }
}
cout << maxi;

Quick Note: #

This approach targets the longest contiguous non-decreasing subarray (which matches the intent of your original code). If you were looking for non-contiguous subsequences, the solution would be different—but this is the right fix for the problem your code is trying to solve.

内容的提问来源于stack exchange，提问作者Sonkun