Linear dynamic programming is a specific approach within dynamic programming used to solve problems with a linear structure. In this paradigm, the states of the problem exhibit a linear relationship, and information is typically stored and transferred using a one-dimensional array. It is commonly applied to problems involving linear sequences or arrays, such as finding Longest Increasing Subsequence (LIS) or the Maximum Subarray Sum.

Longest Increasing Subsequence (LIS)

Longest Increasing Subsequence is a special subsequence of a given sequence where the elements are in increasing order, each element being greater than the preceding one. The goal is to find the subsequence with the maximum length that maintains this property and the original relative order of elements.

For instance, given the sequence [10, 9, 2, 5, 3, 7, 101, 18], the LIS is [2, 3, 7, 101], with a length of 4. The objective is typically to determine this maximum length or the subsequence itself.

Maximum Subarray Sum

Consider a scenario with a salesperson's weekly record: [10, -3, 7, 8, -4, -2, 6]. Each value represents daily sales (in thousands), which can be positive (profit) or negative (loss). The task is to identify the contiguous period (start and end day) that yields the highest total sales.

By analyzing cumulative sums, we can find the optimal subarray. The process involves starting a new cumulative sum whenever the current sum becomes negative, as a negative sum detracts from the total. For the given data, the maximum sum of 22 is achieved from day 4 to day 7.

Solving LIS with Linear Dynamic Programming

We can solve the LIS problem using a dynamic programming approach with the folllowing steps:

1. State Definition: Define a one-dimensional array lis_length, where lis_length[i] represents the length of the longest increasing subsequence ending at element nums[i].
2. State Transition: For each index i, iterate through all previous indices j (from 0 to i-1). If nums[j] < nums[i], then nums[i] can extend the subsequence ending at nums[j]. Update lis_length[i] to be the maximum of its current value and lis_length[j] + 1.
3. Initialization: Each element can form a subsequence of length 1 by itself. Therefore, initialize all values in lis_length to 1.

Here is a Python implementation:

def find_lis_length(sequence):
    if not sequence:
        return 0

    size = len(sequence)
    # Initialize DP array: each element is a subsequence of length 1
    lis_length = [1] * size

    for current_idx in range(1, size):
        for prev_idx in range(current_idx):
            if sequence[current_idx] > sequence[prev_idx]:
                # Update if a longer subsequence is found
                lis_length[current_idx] = max(lis_length[current_idx], lis_length[prev_idx] + 1)

    # The answer is the maximum value in the DP array
    return max(lis_length)

# Example usage
sample_nums = [10, 9, 2, 5, 3, 7, 101, 18]
print("Length of Longest Increasing Subsequence:", find_lis_length(sample_nums))

Solving Maximum Subarray Sum with Linear Dynamic Programming

The Maximum Subarray Sum problem can also be solved efficiently with a linear DP approach, often known as Kadane's Algorithm.

1. State Definition: Define an array max_ending_here, where max_ending_here[i] represants the maximum sum of a subarray ending at index i.
2. State Transition: At each position i, we have two choices: start a new subarray with just nums[i], or extend the previous best subarray ending at i-1. Therefore, max_ending_here[i] = max(nums[i], max_ending_here[i-1] + nums[i]).
3. Initialization: max_ending_here[0] is simply nums[0].

The final answer is the maximum value found in the max_ending_here array.

def find_max_subarray_sum(arr):
    if not arr:
        return 0

    n = len(arr)
    max_ending_here = [0] * n
    max_ending_here[0] = arr[0]

    for i in range(1, n):
        # Choose between starting fresh or extending the previous subarray
        max_ending_here[i] = max(arr[i], max_ending_here[i-1] + arr[i])

    return max(max_ending_here)

# Example usage
test_array = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum Subarray Sum:", find_max_subarray_sum(test_array))