Solve increasing sequence and path problems
Overview
This question evaluates proficiency in longest increasing contiguous subarray detection, longest increasing subsequence computation and reconstruction, and longest increasing path discovery in a grid, testing array manipulation, sequence reconstruction, dynamic programming and graph traversal concepts within the Coding & Algorithms domain.
Answer the following related tasks about increasing sequences and paths:
a) Contiguous subarray: Given an integer array nums, find the longest strictly increasing contiguous subarray. Return the length and the start/end indices of any one such subarray. Example: nums = [1, 2, 1, 2, 3] -> length = 3 with subarray [1, 2, 3]. Target time O(n), space O( 1). State how you break ties when multiple subarrays have the same maximum length.
b) Subsequence (not necessarily contiguous): Given an integer array nums, compute the length of the longest strictly increasing subsequence and reconstruct one valid subsequence. Aim for an O(n log n) algorithm with O(n) space; explain the data structures used and why the approach is correct.
c) Grid path (inspired by a well-known problem): Given an m × n grid of integers, find the length of the longest path that is strictly increasing, where each move goes to one of the four orthogonal neighbors (up, down, left, right). Optionally return one such path. Assume 1 ≤ m, n ≤ 500. Design the algorithm and analyze time and space complexity, detailing how you avoid revisiting states and ensure correctness.