Oleksii Trekhleb | Javascript algorithms (Maximum subarray problem)
This is a series of books diving deep into the core mechanisms of the JavaScript language.
· 1 phút đọc.
![nhavantuonglai This is a series of books diving deep into the core mechanisms of the JavaScript language.](https://data.nhavantuonglai.com/image/illustrations/cover-nhavantuonglai-com-0566.jpg)
The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array, a[1…n]
, of numbers which has the largest sum, where,
Example
The list usually contains both positive and negative numbers along with 0
. For example, for the array of values −2, 1, −3, 4, −1, 2, 1, −5, 4
the contiguous subarray with the largest sum is 4, −1, 2, 1
, with sum 6
.
Solutions
Brute Force solution
O(n^2)
: bfMaximumSubarray.jsDivide and Conquer solution
O(n^2)
: dcMaximumSubarraySum.jsDynamic Programming solution
O(n)
: dpMaximumSubarray.js
![nhavantuonglai nhavantuonglai](https://data.nhavantuonglai.com/image/illustrations/cover-nhavantuonglai-com-0127.jpg)