Longest Subarray with Increasing Sum
MediumPractice library · +20 XPtwo pointerssubarraysliding window
Given an array of N integers, find the length of the longest contiguous subarray whose elements sum to a strictly increasing sequence. That is, for a subarray a[i...j], it must satisfy a[k] < a[k+1] for all i <= k < j.
Input
The first line contains an integer N. The second line contains N space-separated integers.
Output
Print a single integer representing the length of the longest such subarray.
Constraints
1 <= N <= 200000. Each integer in the array is between -10^9 and 10^9.
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 1 2 3 1 2
Output
3
The longest increasing subarray is [1, 2, 3] with length 3.
Example 2
Input
7 10 20 5 15 25 30 35
Output
5
The longest increasing subarray is [5, 15, 25, 30, 35] with length 5.
Hints
Similar problems
- Optimal Training ScheduleMedium
- Longest Subarray with At Most K Distinct ElementsMedium
- Count Subarrays with Distinct ElementsMedium
- Longest Subarray with Bounded DifferenceMedium
- Longest Subarray with Limited DifferenceMedium
- Longest Sorted SubsegmentMedium
More topics: Two Pointers problems, Sliding Window problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 2 3 1 2
Example 2 input
7 10 20 5 15 25 30 35