#dynamic programming

Solutions The brute-force approach to solve this problems involves generating all the possible substrings of the input number. This requires \(O(N^2)\) time, which becomes too expensive in the worst case when the input size can be as large as \(2 \cdot 10^5\). To find an efficient solution, let’s consider the input 8314. All the possible substrings are listed below: 1 2 3 4 8 3 83 1 31 831 4 14 314 8314 Each line contains all the substrings ending with the corresponding digit. [Read More]

Solutions We have two similar tasks: find the maximum sum of any nonempty subarray find the maximum sum of any nonempty subsequence The latter is clearly esier since the elements in a subsequence are not necessarily contiguous. The former is a very classical problem that we’ll deal with in a moment. To solve the first task, we can sum all the positive elements. This works as long as we have at least one positive (or zero) element. [Read More]