- Notifications
You must be signed in to change notification settings - Fork230
Arrays#309
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Merged
Uh oh!
There was an error while loading.Please reload this page.
Merged
Arrays#309
Changes fromall commits
Commits
Show all changes
28 commits Select commitHold shift + click to select a range
042d43f
Arrays
joaquinelio5314f8f
Update 1-js/05-data-types/04-array/10-maximal-subarray/solution.md
joaquineliob3a0cc0
Update 1-js/05-data-types/04-array/10-maximal-subarray/solution.md
joaquinelioaf2e2a0
Update 1-js/05-data-types/04-array/10-maximal-subarray/solution.md
joaquinelioa373976
Update 1-js/05-data-types/04-array/5-array-input-sum/task.md
joaquineliobaa16d7
Update 1-js/05-data-types/04-array/article.md
joaquinelio71793c9
Update 1-js/05-data-types/04-array/article.md
joaquinelio1a517fd
Update 1-js/05-data-types/04-array/article.md
joaquinelioa73a204
Update 1-js/05-data-types/04-array/article.md
joaquinelioe88e22a
Update 1-js/05-data-types/04-array/article.md
joaquineliofef7302
Update 1-js/05-data-types/04-array/5-array-input-sum/task.md
joaquinelio93aedf5
Update 1-js/05-data-types/04-array/2-create-array/task.md
joaquineliocc3750c
Update 1-js/05-data-types/04-array/3-call-array-this/solution.md
joaquinelioc2f4f67
Update 1-js/05-data-types/04-array/3-call-array-this/task.md
joaquinelio05a0618
Update 1-js/05-data-types/04-array/article.md
joaquinelio383249d
Update 1-js/05-data-types/04-array/5-array-input-sum/solution.md
joaquineliof122d1e
Update 1-js/05-data-types/04-array/article.md
joaquinelio8fdb93a
Update 1-js/05-data-types/04-array/article.md
joaquinelio726df56
Update 1-js/05-data-types/04-array/article.md
joaquineliob3e4585
Update 1-js/05-data-types/04-array/article.md
joaquinelio2f951b1
Update 1-js/05-data-types/04-array/article.md
joaquinelio785ff52
Update 1-js/05-data-types/04-array/article.md
joaquineliofe7c1bf
Update 1-js/05-data-types/04-array/article.md
joaquinelio214685f
Update 1-js/05-data-types/04-array/article.md
joaquineliodb4e7fb
Update 1-js/05-data-types/04-array/article.md
joaquinelio778666a
Update article.md
joaquineliobcb2dc4
Update 1-js/05-data-types/04-array/article.md
joaquinelio6a6b3f8
Update 1-js/05-data-types/04-array/10-maximal-subarray/solution.md
joaquinelioFile filter
Filter by extension
Conversations
Failed to load comments.
Loading
Uh oh!
There was an error while loading.Please reload this page.
Jump to
Jump to file
Failed to load files.
Loading
Uh oh!
There was an error while loading.Please reload this page.
Diff view
Diff view
There are no files selected for viewing
4 changes: 2 additions & 2 deletions1-js/05-data-types/04-array/1-item-value/solution.md
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
10 changes: 5 additions & 5 deletions1-js/05-data-types/04-array/1-item-value/task.md
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
44 changes: 22 additions & 22 deletions1-js/05-data-types/04-array/10-maximal-subarray/solution.md
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -1,43 +1,43 @@ | ||
#Solución lenta | ||
Podemos calcular todas las subsumas. | ||
La forma más simple es tomar cada elemento y calcular las sumas de todos lossubarraysque comienzan con él. | ||
Por ejemplo, para `[-1, 2, 3, -9, 11]`: | ||
```js no-beautify | ||
//Comenzando desde -1: | ||
-1 | ||
-1 + 2 | ||
-1 + 2 + 3 | ||
-1 + 2 + 3 + (-9) | ||
-1 + 2 + 3 + (-9) + 11 | ||
//Comenzando desde 2: | ||
2 | ||
2 + 3 | ||
2 + 3 + (-9) | ||
2 + 3 + (-9) + 11 | ||
//Comenzando desde 3: | ||
3 | ||
3 + (-9) | ||
3 + (-9) + 11 | ||
//Comenzando desde -9 | ||
-9 | ||
-9 + 11 | ||
//Comenzando desde 11 | ||
11 | ||
``` | ||
El código es un bucle anidado. El bucle externo itera sobre los elementos del array, y el interno cuenta subsumas comenzando con cada uno de ellos. | ||
```js run | ||
function getMaxSubSum(arr) { | ||
let maxSum = 0; //sinoobtenemos elementos, devolverá cero | ||
joaquinelio marked this conversation as resolved. Show resolvedHide resolvedUh oh!There was an error while loading.Please reload this page. | ||
for (let i = 0; i < arr.length; i++) { | ||
let sumFixedStart = 0; | ||
@@ -57,25 +57,25 @@ alert( getMaxSubSum([1, 2, 3]) ); // 6 | ||
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100 | ||
``` | ||
La solución tiene una complejidad 2 en notación Landau[O(n<sup>2</sup>)](https://es.wikipedia.org/wiki/Notaci%C3%B3n_de_Landau) (coste respecto al tiempo). Es decir, si multiplicamos el tamaño delarraypor 2, el tiempo del algoritmo se multiplicará por 4. | ||
Paraarraysmuy grandes(1000, 10000o más items)tales algoritmos llevarán a una severa lentitud. | ||
#Solución rápida | ||
Recorramos elarrayy registremos la suma parcial actual de los elementos en lavariable `s`.Si `s`se vuelve cero en algún punto, le asignamos `s=0`.El máximo entre todas las sumas parciales`s`será la respuesta. | ||
Si la descripción te resulta demasiado vaga, por favor mira el código. Es bastante corto: | ||
```js run demo | ||
function getMaxSubSum(arr) { | ||
let maxSum = 0; | ||
let partialSum = 0; | ||
for (let item of arr) { //por cada itemde arr | ||
partialSum += item; //se lo suma a partialSum | ||
maxSum = Math.max(maxSum, partialSum); //registra el máximo | ||
if (partialSum < 0) partialSum = 0; //cero si se vuelve negativo | ||
} | ||
return maxSum; | ||
@@ -89,6 +89,6 @@ alert( getMaxSubSum([1, 2, 3]) ); // 6 | ||
alert( getMaxSubSum([-1, -2, -3]) ); // 0 | ||
``` | ||
El algoritmo requiere exactamente una pasada, entonces la complejidad es O(n). | ||
Puedes encontrar información detallada acerca del algoritmo: [Subvector de suma máxima](https://es.wikibooks.org/wiki/Algoritmia/Divide_y_vencer%C3%A1s#Subvector_de_suma_m%C3%A1xima).Si aún no es obvio cómo funciona, traza el algoritmo en los ejemplos de arriba y observa cómo trabaja, es mejor que cualquier explicación. |
18 changes: 9 additions & 9 deletions1-js/05-data-types/04-array/10-maximal-subarray/task.md
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
17 changes: 8 additions & 9 deletions1-js/05-data-types/04-array/2-create-array/task.md
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
6 changes: 3 additions & 3 deletions1-js/05-data-types/04-array/3-call-array-this/solution.md
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
5 changes: 2 additions & 3 deletions1-js/05-data-types/04-array/3-call-array-this/task.md
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
7 changes: 3 additions & 4 deletions1-js/05-data-types/04-array/5-array-input-sum/solution.md
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
12 changes: 6 additions & 6 deletions1-js/05-data-types/04-array/5-array-input-sum/task.md
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
Oops, something went wrong.
Uh oh!
There was an error while loading.Please reload this page.
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.