Prelusion¶

We will have some discussion in Maximum Subsequence Sum. The main question is to solve: For a given sequence \(A_k\), evaluate the function

\[f(i,j) = \max{\left\{\sum_{k=i}^{j} A_{k}\right\}}.\]

Interface¶

Some algorithms to solve Maximum Subsequence Sum.

brute_force_enumeration(arr: list[int]) → int¶

The brute force enumeration method.

Time complexity is \(O(n^3)\). Space complexity is \(O(1)\).

optimized_enumeration(arr: list[int]) → int¶

Optimizes the summation method from brute force enumeration.

Time complexity is \(O(n^2)\). Space complexity is \(O(1)\).

divide_and_conquer(arr: list[int]) → int¶

The Divide and Conquer algorithm.

Time complexity is \(O(n \log n)\). Space complexity is \(O(\log n)\).

dynamic_programming(arr: list[int]) → int¶

The Kadane’s Algorithm (Dynamic Programming).

Time complexity is \(O(n)\). Space complexity is \(O(1)\).