MVCS: Difference between revisions
From charlesreid1
(Created page with "==Problem Description== Given a sequence of integers, <math>a_1, a_2, \dots, a_n</math>, determine the subsequence of integers with the maximum sum. (Note, this problem is...") |
m (Replacing charlesreid1.com:3000 with git.charlesreid1.com) |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
MVCS: Maximum value contiguous subsequence | |||
==Problem Description== | ==Problem Description== | ||
| Line 7: | Line 9: | ||
==Solution== | ==Solution== | ||
https://charlesreid1.com | This is a fairly straightforward dynamic programming problem that just requires evaluating the maximum sum for a sliding window, and store the results in a 1D array. | ||
https://git.charlesreid1.com/cs/java/src/master/dynamic-programming/max-val-seq | |||
==Flags== | ==Flags== | ||
Latest revision as of 03:38, 9 October 2019
MVCS: Maximum value contiguous subsequence
Problem Description
Given a sequence of integers, $ a_1, a_2, \dots, a_n $, determine the subsequence of integers with the maximum sum.
(Note, this problem is only interesting if there are negative numbers.)
Solution
This is a fairly straightforward dynamic programming problem that just requires evaluating the maximum sum for a sliding window, and store the results in a 1D array.
https://git.charlesreid1.com/cs/java/src/master/dynamic-programming/max-val-seq
Flags
 |
Combinatorics
Combinatorial Structures - Order Does Not Matter Ordinary generating functions
Labelled Structures - Order Matters Enumerating Permutations: String Permutations Generating Permutations: Cool · Algorithm M (add-one) · Algorithm G (Gray binary code)
Combinatorics Problems Longest Increasing Subsequence · Maximum Value Contiguous Subsequence · Racing Gems Cards (poker hands with a deck of 52 playing cards)
|
 |
Algorithms Part of Computer Science Notes
Series on Algorithms
Algorithms/Sort · Algorithmic Analysis of Sort Functions · Divide and Conquer · Divide and Conquer/Master Theorem Three solid O(n log n) search algorithms: Merge Sort · Heap Sort · Quick Sort Algorithm Analysis/Merge Sort · Algorithm Analysis/Randomized Quick Sort
Algorithms/Search · Binary Search · Binary Search Modifications
Algorithms/Combinatorics · Algorithms/Combinatorics and Heuristics · Algorithms/Optimization · Divide and Conquer
Algorithms/Strings · Algorithm Analysis/Substring Pattern Matching
Algorithm complexity · Theta vs Big O Amortization · Amortization/Aggregate Method · Amortization/Accounting Method Algorithm Analysis/Matrix Multiplication
Estimation Estimation · Estimation/BitsAndBytes
Algorithm Practice and Writeups Project Euler · Five Letter Words · Letter Coverage
|