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

Commit0a062d4

Browse files
Add tests for Kadane algorithm (TheAlgorithms#2877) (TheAlgorithms#2939)
Co-authored-by: Andrii Siriak <siryaka@gmail.com>
1 parentadadb2f commit0a062d4

File tree

2 files changed

+89
-46
lines changed

2 files changed

+89
-46
lines changed
Lines changed: 26 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -1,54 +1,34 @@
1-
packagecom.thealgorithms.dynamicprogramming;
1+
/** Author : Siddhant Swarup Mallick
2+
* Github : https://github.com/siddhant2002
3+
*/
24

3-
importjava.util.Scanner;
5+
/** Program description - To find the maximum subarray sum */
6+
packagecom.thealgorithms.dynamicprogramming;
47

5-
/**
6-
* Program to implement Kadane’s Algorithm to calculate maximum contiguous
7-
* subarray sum of an array Time Complexity: O(n)
8-
*
9-
* @author Nishita Aggarwal
10-
*/
118
publicclassKadaneAlgorithm {
12-
13-
/**
14-
* This method implements Kadane's Algorithm
15-
*
16-
* @param arr The input array
17-
* @return The maximum contiguous subarray sum of the array
18-
*/
19-
staticintlargestContiguousSum(intarr[]) {
20-
inti,len =arr.length,cursum =0,maxsum =Integer.MIN_VALUE;
21-
if (len ==0)// empty array
9+
publicstaticbooleanmax_Sum(inta[] ,intpredicted_answer)
10+
{
11+
intsum=a[0],running_sum=0;
12+
for(intk:a)
2213
{
23-
return0;
14+
running_sum=running_sum+k;
15+
// running sum of all the indexs are stored
16+
sum=Math.max(sum,running_sum);
17+
// the max is stored inorder to the get the maximum sum
18+
if(running_sum<0)
19+
running_sum=0;
20+
// if running sum is negative then it is initialized to zero
2421
}
25-
for (i =0;i <len;i++) {
26-
cursum +=arr[i];
27-
if (cursum >maxsum) {
28-
maxsum =cursum;
29-
}
30-
if (cursum <=0) {
31-
cursum =0;
32-
}
33-
}
34-
returnmaxsum;
22+
// for-each loop is used to iterate over the array and find the maximum subarray sum
23+
returnsum==predicted_answer;
24+
// It returns true if sum and predicted answer matches
25+
// The predicted answer is the answer itself. So it always return true
3526
}
36-
3727
/**
38-
* Main method
39-
*
40-
* @param args Command line arguments
28+
* OUTPUT :
29+
* Input - {89,56,98,123,26,75,12,40,39,68,91}
30+
* Output: it returns either true or false
31+
* 1st approach Time Complexity : O(n)
32+
* Auxiliary Space Complexity : O(1)
4133
*/
42-
publicstaticvoidmain(String[]args) {
43-
Scannersc =newScanner(System.in);
44-
intn,arr[],i;
45-
n =sc.nextInt();
46-
arr =newint[n];
47-
for (i =0;i <n;i++) {
48-
arr[i] =sc.nextInt();
49-
}
50-
intmaxContSum =largestContiguousSum(arr);
51-
System.out.println(maxContSum);
52-
sc.close();
53-
}
54-
}
34+
}
Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
packagecom.thealgorithms.others;
2+
importorg.junit.jupiter.api.Test;
3+
importstaticorg.junit.jupiter.api.Assertions.*;
4+
5+
importcom.thealgorithms.dynamicprogramming.KadaneAlgorithm;
6+
publicclassKadaneAlogrithmTest {
7+
@Test
8+
voidtestForOneElement()
9+
{
10+
inta[]={-1};
11+
assertTrue(KadaneAlgorithm.max_Sum(a,-1));
12+
}
13+
14+
@Test
15+
voidtestForTwoElements()
16+
{
17+
inta[]={-2,1};
18+
assertTrue(KadaneAlgorithm.max_Sum(a,1));
19+
}
20+
21+
@Test
22+
voidtestForThreeElements()
23+
{
24+
inta[]={5,3,12};
25+
assertTrue(KadaneAlgorithm.max_Sum(a,20));
26+
}
27+
28+
@Test
29+
voidtestForFourElements()
30+
{
31+
inta[]={-1,-3,-7,-4};
32+
assertTrue(KadaneAlgorithm.max_Sum(a,-1));
33+
}
34+
35+
@Test
36+
voidtestForFiveElements()
37+
{
38+
inta[]={4,5,3,0,2};
39+
assertTrue(KadaneAlgorithm.max_Sum(a,14));
40+
}
41+
42+
43+
@Test
44+
voidtestForSixElements()
45+
{
46+
inta[]={-43,-45,47,12,87,-13};
47+
assertTrue(KadaneAlgorithm.max_Sum(a,146));
48+
}
49+
50+
@Test
51+
voidtestForSevenElements()
52+
{
53+
inta[]={9,8,2,23,13,6,7};
54+
assertTrue(KadaneAlgorithm.max_Sum(a,68));
55+
}
56+
57+
@Test
58+
voidtestForEightElements()
59+
{
60+
inta[]={9,-5,-5,-2,4,5,0,1};
61+
assertTrue(KadaneAlgorithm.max_Sum(a,10));
62+
}
63+
}

0 commit comments

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