Repository: TheAlgorithms/Java
Pull request #2939 (2022-02-12 16:25:54)

Fixes(#2877)
### **Describe your change:**

- [x] Add an algorithm?
- [ ] Fix a bug or typo in an existing algorithm?
- [ ] Documentation change?

#### References

<!-- Add any reference to previous pull-request or issue -->

### **Checklist:**

<!-- Remove items that do not apply. For completed items, change [ ] to [x]. -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized.
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All new Java files are placed inside an existing directory.
- [x] All filenames are in all uppercase characters with no spaces or dashes.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
- [x] If this pull request resolves one or more open issues then the commit message contains `Fixes: #{$ISSUE_NO}`.



Patch:
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/KadaneAlgorithm.java b/src/main/java/com/thealgorithms/dynamicprogramming/KadaneAlgorithm.java
index 364d16a3..ab15ba17 100644
--- a/src/main/java/com/thealgorithms/dynamicprogramming/KadaneAlgorithm.java
+++ b/src/main/java/com/thealgorithms/dynamicprogramming/KadaneAlgorithm.java
@@ -1,54 +1,34 @@
-package com.thealgorithms.dynamicprogramming;
+/** Author : Siddhant Swarup Mallick
+ * Github : https://github.com/siddhant2002
+ */
 
-import java.util.Scanner;
+/** Program description - To find the maximum subarray sum */
+ package com.thealgorithms.dynamicprogramming;
 
-/**
- * Program to implement Kadane’s Algorithm to calculate maximum contiguous
- * subarray sum of an array Time Complexity: O(n)
- *
- * @author Nishita Aggarwal
- */
 public class KadaneAlgorithm {
-
-    /**
-     * This method implements Kadane's Algorithm
-     *
-     * @param arr The input array
-     * @return The maximum contiguous subarray sum of the array
-     */
-    static int largestContiguousSum(int arr[]) {
-        int i, len = arr.length, cursum = 0, maxsum = Integer.MIN_VALUE;
-        if (len == 0) // empty array
+    public static boolean max_Sum(int a[] , int predicted_answer)
+    {
+        int sum=a[0],running_sum=0;
+        for(int k:a)
         {
-            return 0;
+            running_sum=running_sum+k;
+            // running sum of all the indexs are stored
+            sum=Math.max(sum,running_sum);
+            // the max is stored inorder to the get the maximum sum
+            if(running_sum<0)
+            running_sum=0;
+            // if running sum is negative then it is initialized to zero
         }
-        for (i = 0; i < len; i++) {
-            cursum += arr[i];
-            if (cursum > maxsum) {
-                maxsum = cursum;
-            }
-            if (cursum <= 0) {
-                cursum = 0;
-            }
-        }
-        return maxsum;
+        // for-each loop is used to iterate over the array and find the maximum subarray sum
+        return sum==predicted_answer;
+        // It returns true if sum and predicted answer matches
+        // The predicted answer is the answer itself. So it always return true
     }
-
     /**
-     * Main method
-     *
-     * @param args Command line arguments
+     * OUTPUT :
+     * Input - {89,56,98,123,26,75,12,40,39,68,91}
+     * Output: it returns either true or false
+     * 1st approach Time Complexity : O(n)
+     * Auxiliary Space Complexity : O(1)
      */
-    public static void main(String[] args) {
-        Scanner sc = new Scanner(System.in);
-        int n, arr[], i;
-        n = sc.nextInt();
-        arr = new int[n];
-        for (i = 0; i < n; i++) {
-            arr[i] = sc.nextInt();
-        }
-        int maxContSum = largestContiguousSum(arr);
-        System.out.println(maxContSum);
-        sc.close();
-    }
-}
+}
\ No newline at end of file


Test patch:
diff --git a/src/test/java/com/thealgorithms/others/KadaneAlogrithmTest.java b/src/test/java/com/thealgorithms/others/KadaneAlogrithmTest.java
new file mode 100644
index 00000000..a4934b7e
--- /dev/null
+++ b/src/test/java/com/thealgorithms/others/KadaneAlogrithmTest.java
@@ -0,0 +1,63 @@
+package com.thealgorithms.others;
+import org.junit.jupiter.api.Test;
+import static org.junit.jupiter.api.Assertions.*;
+
+import com.thealgorithms.dynamicprogramming.KadaneAlgorithm;
+public class KadaneAlogrithmTest {
+    @Test
+	void testForOneElement() 
+	{
+        int a[]={-1};
+		assertTrue(KadaneAlgorithm.max_Sum(a,-1));
+	}
+
+	@Test
+	void testForTwoElements() 
+	{
+        int a[]={-2,1};
+		assertTrue(KadaneAlgorithm.max_Sum(a,1));
+	}
+
+	@Test
+	void testForThreeElements() 
+	{
+		int a[]={5,3,12};
+		assertTrue(KadaneAlgorithm.max_Sum(a,20));
+	}
+
+	@Test
+	void testForFourElements() 
+	{
+		int a[]={-1,-3,-7,-4};
+		assertTrue(KadaneAlgorithm.max_Sum(a,-1));
+	}
+
+	@Test
+	void testForFiveElements() 
+	{
+		int a[]={4,5,3,0,2};
+		assertTrue(KadaneAlgorithm.max_Sum(a,14));
+	}
+
+
+	@Test
+	void testForSixElements() 
+	{
+		int a[]={-43,-45,47,12,87,-13};
+		assertTrue(KadaneAlgorithm.max_Sum(a,146));
+	}
+
+	@Test
+	void testForSevenElements() 
+	{
+		int a[]={9,8,2,23,13,6,7};
+		assertTrue(KadaneAlgorithm.max_Sum(a,68));
+    }
+
+	@Test
+	void testForEightElements() 
+	{
+		int a[]={9,-5,-5,-2,4,5,0,1};
+		assertTrue(KadaneAlgorithm.max_Sum(a,10));
+	}
+}
\ No newline at end of file