Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6aa3314

Browse files
authored
fix: fixed error in the MaxProductOfThree algorithm (TheAlgorithms#1295)
* fix: fixed error in the MaxProductOfThree algorithmFixed the error in the MaxProductOfThree by initializing the max and minvariables to null instead of -1. The checks were then altered to checkfor null instead of -1.Also wrote more tests, which randomly generated small arrays andcompared the output of the maxProductOfThree-algorithm to the output ofa slower, but complete, function which calculates all posibletriple-products of the values of the array.Fixes:TheAlgorithms#1294* fix: Added newlines at the end of the files
1 parent5ce828b commit6aa3314

File tree

2 files changed

+59
-6
lines changed

2 files changed

+59
-6
lines changed

‎Dynamic-Programming/MaxProductOfThree.js

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -10,25 +10,25 @@ export function maxProductOfThree (arrayItems) {
1010
constn=arrayItems.length
1111
if(n<3)thrownewError('Triplet cannot exist with the given array')
1212
letmax1=arrayItems[0]
13-
letmax2=-1
14-
letmax3=-1
13+
letmax2=null
14+
letmax3=null
1515
letmin1=arrayItems[0]
16-
letmin2=-1
16+
letmin2=null
1717
for(leti=1;i<n;i++){
1818
if(arrayItems[i]>max1){
1919
max3=max2
2020
max2=max1
2121
max1=arrayItems[i]
22-
}elseif(max2===-1||arrayItems[i]>max2){
22+
}elseif(max2===null||arrayItems[i]>max2){
2323
max3=max2
2424
max2=arrayItems[i]
25-
}elseif(max3===-1||arrayItems[i]>max3){
25+
}elseif(max3===null||arrayItems[i]>max3){
2626
max3=arrayItems[i]
2727
}
2828
if(arrayItems[i]<min1){
2929
min2=min1
3030
min1=arrayItems[i]
31-
}elseif(min2===-1||arrayItems[i]<min2){
31+
}elseif(min2===null||arrayItems[i]<min2){
3232
min2=arrayItems[i]
3333
}
3434
}

‎Dynamic-Programming/tests/MaxProductOfThree.test.js

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,3 +15,56 @@ describe('MaxProductOfThree', () => {
1515
expect(maxProductOfThree([10,-6,5,3,1,-10])).toBe(600)
1616
})
1717
})
18+
19+
// Tests using random arrays of size 3 to 5, with values rangin from -4 to 4
20+
// The output is compared to a slower function that calculates all possible products of 3 numbers in the array and returns the largest one
21+
describe('MaxProductOfThree, random arrays of size 3 to 5',()=>{
22+
// Slower function that operates in O(n^3), where n is the length of the input array.
23+
// Calculates all possible products of 3 numbers in the array and returns the largest
24+
functioncompleteMaxThree(array){
25+
letmaximumProduct=null
26+
for(leti=0;i<array.length-2;i++){
27+
for(letj=i+1;j<array.length-1;j++){
28+
for(letk=j+1;k<array.length;k++){
29+
constcurrentProduct=array[i]*array[j]*array[k]
30+
if(maximumProduct===null||currentProduct>maximumProduct){
31+
maximumProduct=currentProduct
32+
}
33+
}
34+
}
35+
}
36+
returnmaximumProduct
37+
}
38+
39+
// Set up consts for the tests
40+
constmaxValue=4
41+
constminValue=-4
42+
constmaxLength=5
43+
constminLength=3
44+
constnumberOfRandomTests=5000
45+
46+
// Run each test
47+
for(leti=0;i<numberOfRandomTests;i++){
48+
constarr=[]
49+
// Randomize the length of the array in the current test
50+
constlength=Math.floor(Math.random()*(maxLength-minLength)+minLength)
51+
52+
// Fill the array with random values in the specified range
53+
for(letj=0;j<length+1;j++){
54+
arr.push(Math.floor(Math.random()*(maxValue-minValue)+minValue))
55+
}
56+
57+
// Calculate the actual max product, slow but completely
58+
constexpectedProduct=completeMaxThree(arr)
59+
60+
// Set up the expectation
61+
it('Expect the array '+arr.toString()+' to return the maximum three product of '+expectedProduct,()=>{
62+
// Calculate the max three product using the function being tested
63+
constactualProduct=maxProductOfThree(arr)
64+
65+
// Was unable to use expect().toBe(), since it sometimes compared 0 to -0, and that would not pass
66+
// At the same time, standardjs forbid me from checking for === -0 to convert to 0
67+
expect(actualProduct===expectedProduct).toBeTruthy()
68+
})
69+
}
70+
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp