ChunYu's Algorithm Library
  1. 0. 1/0 Knapsack Problem
  2. 0. Bike Rental Scheduling
  3. 0. Max Sum Increasing Subsequence
  4. 1. Two Sum
  5. 19. Remove Nth Node From End of List
  6. 35. Insert Search Position
  7. 45. Jump Game II
  8. 53. Maximum Subarray
  9. 63. Unique Paths II
  10. 70. Climbing Stairs
  11. 72. Edit Distance (Levenshtein Distance)
  12. 75. Sort Colors (Dutch National Flag)
  13. 78. Subsets (Power Set)
  14. 136. Single Number
  15. 141. Linked List Cycle
  16. 150. Evaluate Reverse Polish Notation
  17. 160. Intersection of Two Linked Lists
  18. 169. Majority Element
  19. 200. Number of Islands
  20. 210. Course Schedule II
  21. 215. Kth Largest Element in an Array
  22. 226. Invert Binary Tree
  23. 231. Power of Two
  24. 234. Palindrome Linked List
  25. 237. Delete a Node in a Linked List
  26. 279. Perfect Squares
  27. 322. Coin Change
  28. 323. Number of Connected Components in an Undirected Graph
  29. 344. Reverse a String
  30. 380. Insert Delete GetRandom O(1)
  31. 383. Ransom Note
  32. 392. Is Subsequence
  33. 406. Queue Reconstruction by Height
  34. 417. Pacific Atlantic Water Flow
  35. 468. Validate IP Address
  36. 490. The Maze
  37. 509. Fibonacci Number
  38. 518. Coin Change II
  39. 520. Detect Capital
  40. 528. Random Pick with Weight
  41. 690. Employee Importance
  42. 700. Search in a Binary Search Tree
  43. 703. Kth Largest Element in a Stream
  44. 705. Design Hashset
  45. 706. Design Hashmap
  46. 733. Flood Fill
  47. 912. Sort an Array
  48. 933. Number of Recent Calls
  49. 994. Rotting Oranges
  50. 1029. Two City Scheduling
  51. 1431. Kids with Greatest Number of Candies
  52. 1436. Destination City
  53. 1437. Check If All 1's are at Least Length K Places Away
  54. 1446. Consecutive Characters
  55. 1447. Simplified Fractions
  56. .

© 2020 ChunYu Shi

0. Max Sum Increasing Subsequence

Last Updated: 2020.06.01

Table of Contents

Resources

Question Source: Code Interview Gym Github
Resources: AlgoExpert.io

Description

Given a non-empty array of integers, write a function that returns an array of length 2. The first element in the output array should be an integer value representing the greatest sum that can be generated from a strictly-increasing subsequence in the array. The second element should be an array of the numbers in that subsequence. A subsequence is deemed as a set of numbers that are not necessarily adjacent but that are in the same order as they appear in the array. Assume that there will only be one increasing subsequence with the greatest sum.

Sample input: [10, 70, 20, 30, 50, 11, 30]
Sample output: [110, [10, 20, 30, 50]]

Dynamic Programming

image