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

Commit814fa77

Browse files
committed
Add more test cases for finding max sub-array algorithm.
1 parent2a2b5da commit814fa77

File tree

3 files changed

+21
-14
lines changed

3 files changed

+21
-14
lines changed

‎src/algorithms/sets/maximum-subarray/__test__/bfMaximumSubarray.test.js

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,10 @@ import bfMaximumSubarray from '../bfMaximumSubarray';
33
describe('bfMaximumSubarray',()=>{
44
it('should find maximum subarray using brute force algorithm',()=>{
55
expect(bfMaximumSubarray([])).toEqual([]);
6+
expect(bfMaximumSubarray([0,0])).toEqual([0]);
7+
expect(bfMaximumSubarray([0,0,1])).toEqual([0,0,1]);
8+
expect(bfMaximumSubarray([0,0,1,2])).toEqual([0,0,1,2]);
9+
expect(bfMaximumSubarray([0,0,-1,2])).toEqual([2]);
610
expect(bfMaximumSubarray([-1,-2,-3,-4,-5])).toEqual([-1]);
711
expect(bfMaximumSubarray([1,2,3,2,3,4,5])).toEqual([1,2,3,2,3,4,5]);
812
expect(bfMaximumSubarray([-2,1,-3,4,-1,2,1,-5,4])).toEqual([4,-1,2,1]);

‎src/algorithms/sets/maximum-subarray/__test__/dpMaximumSubarray.test.js

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,10 @@ import dpMaximumSubarray from '../dpMaximumSubarray';
33
describe('dpMaximumSubarray',()=>{
44
it('should find maximum subarray using dynamic programming algorithm',()=>{
55
expect(dpMaximumSubarray([])).toEqual([]);
6+
expect(dpMaximumSubarray([0,0])).toEqual([0]);
7+
expect(dpMaximumSubarray([0,0,1])).toEqual([0,0,1]);
8+
expect(dpMaximumSubarray([0,0,1,2])).toEqual([0,0,1,2]);
9+
expect(dpMaximumSubarray([0,0,-1,2])).toEqual([2]);
610
expect(dpMaximumSubarray([-1,-2,-3,-4,-5])).toEqual([-1]);
711
expect(dpMaximumSubarray([1,2,3,2,3,4,5])).toEqual([1,2,3,2,3,4,5]);
812
expect(dpMaximumSubarray([-2,1,-3,4,-1,2,1,-5,4])).toEqual([4,-1,2,1]);

‎src/algorithms/sets/maximum-subarray/dpMaximumSubarray.js

Lines changed: 13 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -6,36 +6,35 @@
66
*@return {Number[]}
77
*/
88
exportdefaultfunctiondpMaximumSubarray(inputArray){
9-
// We iterate through the inputArray once, using a greedy approach
10-
//to keep track of the maximumsum we've seen so far and the current sum
9+
// We iterate through the inputArray once, using a greedy approach to keep track of the maximum
10+
// sum we've seen so far and the current sum.
1111
//
12-
// currentSum gets reset to 0everytimeit drops below 0
12+
//ThecurrentSumvariablegets reset to 0every timeit drops below 0.
1313
//
14-
// maxSum is set to -Infinity so that if all numbers
15-
//arenegative, the highest negativenumber will constitute
16-
// the maximum subarray
14+
//ThemaxSumvariableis set to -Infinity so that if all numbers are negative, the highest
15+
// negativenumber will constitute the maximum subarray.
16+
1717
letmaxSum=-Infinity;
1818
letcurrentSum=0;
1919

20-
// We need to keep track of the starting and ending indices that
21-
//contributed to our maxSumso that we can return the actual subarray
20+
// We need to keep track of the starting and ending indices that contributed to our maxSum
21+
// so that we can return the actual subarray.
2222
letmaxStartIndex=0;
2323
letmaxEndIndex=inputArray.length;
24+
2425
letcurrentStartIndex=0;
2526

26-
inputArray.forEach((num,currentIndex)=>{
27-
currentSum+=num;
27+
inputArray.forEach((currentNumber,currentIndex)=>{
28+
currentSum+=currentNumber;
2829

29-
// Update maxSum and the corresponding indices
30-
// if we have found a new max
30+
// Update maxSum and the corresponding indices if we have found a new max.
3131
if(maxSum<currentSum){
3232
maxSum=currentSum;
3333
maxStartIndex=currentStartIndex;
3434
maxEndIndex=currentIndex+1;
3535
}
3636

37-
// Reset currentSum and currentStartIndex
38-
// if currentSum drops below 0
37+
// Reset currentSum and currentStartIndex if currentSum drops below 0.
3938
if(currentSum<0){
4039
currentSum=0;
4140
currentStartIndex=currentIndex+1;

0 commit comments

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