Create Max Sum Contiguous Subarray .java

raysangita27 · web-flow · commit f229dd6e880b · 2020-07-27T01:33:26.000+05:30
diff --git a/Array/Max Sum Contiguous Subarray .java b/Array/Max Sum Contiguous Subarray .java
@@ -0,0 +1,55 @@
+/*
+Find the contiguous subarray within an array, A of length N which has the largest sum.
+
+Input Format:
+
+The first and the only argument contains an integer array, A.
+Output Format:
+
+Return an integer representing the maximum possible sum of the contiguous subarray.
+Constraints:
+
+1 <= N <= 1e6
+-1000 <= A[i] <= 1000
+For example:
+
+Input 1:
+    A = [1, 2, 3, 4, -10]
+
+Output 1:
+    10
+
+Explanation 1:
+    The subarray [1, 2, 3, 4] has the maximum possible sum of 10.
+
+Input 2:
+    A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
+
+Output 2:
+    6
+
+Explanation 2:
+    The subarray [4,-1,2,1] has the maximum possible sum of 6.
+ */
+ 
+ 
+ public class Solution {
+    // DO NOT MODIFY THE LIST. IT IS READ ONLY
+    public int maxSubArray(final List<Integer> A) {
+        int len = A.size();
+        if(len == 0)
+            return 0;
+        int sum = 0; 
+        int maxSum = Integer.MIN_VALUE;
+        for(int i = 0; i<len; i++)
+        {
+            sum = Math.max(sum+A.get(i), A.get(i) );
+            maxSum = Math.max(maxSum , sum);
+        }
+        return maxSum;
+    }
+}
+
+ 
+ 
+ 
