1.2 Longest Ascending Subarray (contiguous)

Assumption: given array is not null

Input: int[] array

Output: int the length of the longest ascending subarray

index 0 1 2 3 4 5 6 7

input[] 7 2 3 1 5 8 9 6

dp[] 1 1 2 1 2 3 4 1

Solution:

1. Base case: dp[0] = 1

2. Induction rule: dp[i] represents from the index 0th to ith, the length of longest ascending subarray ends at the ith element, inclusive.

dp[i] = 1 + dp[i-1], if input[i] > input[i-1]

otherwise, dp[i] = 1

3. No need to store all dp[i], only maintain a current global max length

TC: n = array.length = O(n)

SC: if store all dp[i] = O(n), optimized to O(1)

public int longest(int[] array) {
  if (array.length == 0) {
    return 0;
  }
  int cur = 1;
  int res = 1;
  for (int i = 1; i < array.length; i++) {
    if (array[i] > array[i - 1]) {
      cur++;
      res = Math.max(res, cur);
    } else {
      cur = 1;
    }
  }
  return res;
}