Financial Trends — Problem Statement & Solution Guide
Problem Description
Given an array of integers representing daily stock prices, identify the length of the longest contiguous subarray that first strictly increases (each price higher than the previous) and then strictly decreases (each price lower than the previous). Both the increasing part and the decreasing part must contain at least one element; a subarray that is only increasing or only decreasing does not qualify. Return the maximum length found, or 0 if no such subarray exists.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Financial Trends"
WHY DOES IT MATTER?
Bitonic patterns appear in stock analysis, signal processing, and performance profiling, where identifying a rise‑then‑fall trend is crucial for decision making. Mastering this pattern sharpens a candidate’s ability to combine forward and backward scans, a technique reusable in many array‑based problems.
OPTIMIZATION CHALLENGE
The key insight is that the longest valid subarray is anchored at a peak; by precomputing increasing lengths ending at each index and decreasing lengths starting at each index, we reduce the combinatorial explosion to a simple linear merge.
REAL-WORLD CONNECTION
Think of a distributed load balancer that first ramps up traffic to a server (increase) and then throttles it down (decrease). Detecting the longest such ramp‑down cycle mirrors the longest bitonic subarray computation.
During an interview, compute inc[i] on the fly while scanning forward, store it, then compute dec[i] in a reverse pass; finally, a single loop over i yields the answer—no nested loops, no extra complexity.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem is a classic longest bitonic subarray challenge. A bitonic subarray first strictly rises and then strictly falls, and both phases must contain at least one element. A naive solution would examine every possible subarray, checking the monotonicity of each, which leads to O(n^3) time for large n and quickly exceeds limits. The optimal paradigm leverages dynamic programming in two linear scans: one forward pass computes the length of the strictly increasing run ending at each index, and a backward pass computes the length of the strictly decreasing run starting at each index. By merging these two auxiliary arrays, we can evaluate every potential peak in O(1) and obtain the maximum length of a valid bitonic subarray in overall O(n) time and O(n) extra space (or O(1) space with on‑the‑fly calculations). This approach scales to massive input sizes because each element is visited a constant number of times, eliminating redundant comparisons inherent in brute‑force methods.
Interview Questions on This Problem
Q1How would you modify the solution if the subarray is allowed to be only increasing or only decreasing?
Compute the same inc and dec arrays, but treat a peak with inc[i]==1 or dec[i]==1 as a valid candidate; the answer becomes max(maxInc, maxDec, maxBitonic) where maxInc is the longest increasing run and maxDec the longest decreasing run.
Q2Can you solve the problem in O(1) extra space? Explain the trade‑offs.
Yes, by maintaining two counters while scanning: one for the length of the current increasing segment and another for the decreasing segment after a peak, resetting appropriately when the monotonicity breaks. This single‑pass method avoids the auxiliary arrays but requires careful state management to handle overlapping peaks.
Q3Why does the strict inequality matter, and how would you handle equal adjacent prices?
Strict inequality ensures no plateau is considered part of either the rise or fall; when equal values appear, they break both increasing and decreasing sequences, so you must reset counters or treat them as boundaries in the DP arrays.
Examples
Input
[2,4,6,5,3,1,2,3]
Output
6
Explanation: The segment 2,4,6,5,3,1 rises from 2→4→6 and then falls 6→5→3→1, giving a total length of 6. No longer qualifying segment exists.
Input
[1,3,5,4,2,6,8,7]
Output
5
Explanation: Two qualifying segments exist: 1,3,5,4,2 (length 5) and 6,8,7 (length 3). The longest has length 5.
Input
[5,4,3,2,1]
Output
0
Explanation: The array never increases before decreasing, so no valid segment is present; the answer is 0.
Constraints
- 1 <= nums.length <= 100000
- -1000000000 <= nums[i] <= 1000000000
- Solution must run in O(n) time and O(1) additional space
Optimal Approach & Strategy
Use two linear passes to compute increasing and decreasing run lengths, then combine them in a final pass to obtain the longest bitonic subarray in O(n) time.
Brute Force Approach
Check every possible subarray, verify if it first increases then decreases, and keep the maximum length—this costs O(n^3) time.
Verified Code Solutions
/**
* @param {number[]} prices
* @return {number}
*/
function longestFinancialTrend(prices) {
const n = prices.length;
if (n < 3) return 0;
let maxLen = 0;
let i = 0;
while (i < n - 1) {
// Find the start of an increasing sequence
if (prices[i] < prices[i + 1]) {
const start = i;
// Extend the increasing part
while (i < n - 1 && prices[i] < prices[i + 1]) {
i++;
}
// Now i is at the peak
// Check if there is a decreasing part
if (i < n - 1 && prices[i] > prices[i + 1]) {
// Extend the decreasing part
while (i < n - 1 && prices[i] > prices[i + 1]) {
i++;
}
// The subarray is from start to i
const len = i - start + 1;
maxLen = Math.max(maxLen, len);
}
} else {
i++;
}
}
return maxLen;
}
// Driver code
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split('\n');
const n = parseInt(input[0]);
const prices = input[1].split(' ').map(Number);
console.log(longestFinancialTrend(prices));#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int longestFinancialTrend(vector<int>& prices) {
int n = prices.size();
if (n < 3) return 0;
int maxLen = 0;
int i = 0;
while (i < n - 1) {
// Find the start of an increasing sequence
if (prices[i] < prices[i + 1]) {
int start = i;
// Extend the increasing part
while (i < n - 1 && prices[i] < prices[i + 1]) {
i++;
}
// Now i is at the peak (or end of increasing part)
int peak = i;
// Check if there is a decreasing part
if (i < n - 1 && prices[i] > prices[i + 1]) {
int decStart = i;
// Extend the decreasing part
while (i < n - 1 && prices[i] > prices[i + 1]) {
i++;
}
// The subarray is from start to i
int len = i - start + 1;
maxLen = max(maxLen, len);
} else {
// No decreasing part, so this increasing sequence doesn't qualify
// Move to next potential start
}
} else {
i++;
}
}
return maxLen;
}
int main() {
int n;
cin >> n;
vector<int> prices(n);
for (int i = 0; i < n; i++) {
cin >> prices[i];
}
cout << longestFinancialTrend(prices) << endl;
return 0;
}import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static int longestFinancialTrend(List<Integer> prices) {
int n = prices.size();
if (n < 3) return 0;
int maxLen = 0;
int i = 0;
while (i < n - 1) {
// Find the start of an increasing sequence
if (prices.get(i) < prices.get(i + 1)) {
int start = i;
// Extend the increasing part
while (i < n - 1 && prices.get(i) < prices.get(i + 1)) {
i++;
}
// Now i is at the peak
// Check if there is a decreasing part
if (i < n - 1 && prices.get(i) > prices.get(i + 1)) {
// Extend the decreasing part
while (i < n - 1 && prices.get(i) > prices.get(i + 1)) {
i++;
}
// The subarray is from start to i
int len = i - start + 1;
maxLen = Math.max(maxLen, len);
}
} else {
i++;
}
}
return maxLen;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<Integer> prices = new ArrayList<>();
for (int i = 0; i < n; i++) {
prices.add(sc.nextInt());
}
System.out.println(longestFinancialTrend(prices));
}
}def longest_financial_trend(prices):
"""
Find the length of the longest contiguous subarray that first strictly
increases and then strictly decreases. Both parts must have at least one element.
:param prices: List[int]
:return: int
"""
n = len(prices)
if n < 3:
return 0
max_len = 0
i = 0
while i < n - 1:
# Find the start of an increasing sequence
if prices[i] < prices[i + 1]:
start = i
# Extend the increasing part
while i < n - 1 and prices[i] < prices[i + 1]:
i += 1
# Now i is at the peak
# Check if there is a decreasing part
if i < n - 1 and prices[i] > prices[i + 1]:
# Extend the decreasing part
while i < n - 1 and prices[i] > prices[i + 1]:
i += 1
# The subarray is from start to i
length = i - start + 1
max_len = max(max_len, length)
else:
i += 1
return max_len
if __name__ == "__main__":
import sys
input_data = sys.stdin.read().split()
n = int(input_data[0])
prices = list(map(int, input_data[1:n+1]))
print(longest_financial_trend(prices))/**
* @param {number[]} prices
* @return {number}
*/
function longestFinancialTrend(prices) {
const n = prices.length;
if (n < 3) return 0;
let maxLen = 0;
let i = 0;
while (i < n - 1) {
// Find the start of an increasing sequence
if (prices[i] < prices[i + 1]) {
const start = i;
// Extend the increasing part
while (i < n - 1 && prices[i] < prices[i + 1]) {
i++;
}
// Now i is at the peak
// Check if there is a decreasing part
if (i < n - 1 && prices[i] > prices[i + 1]) {
// Extend the decreasing part
while (i < n - 1 && prices[i] > prices[i + 1]) {
i++;
}
// The subarray is from start to i
const len = i - start + 1;
maxLen = Math.max(maxLen, len);
}
} else {
i++;
}
}
return maxLen;
}
// Driver code
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split('\n');
const n = parseInt(input[0]);
const prices = input[1].split(' ').map(Number);
console.log(longestFinancialTrend(prices));Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.