Commit62fdf0d

committed

Kadane's Algorithm added

1 parent6efaddb commit62fdf0dCopy full SHA for 62fdf0d

File tree

+55

-0

lines changed

+55

-0

lines changed

Lines changed: 55 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,55 @@`
	`1`	`+importjava.util.Scanner;`
	`2`	`+`
	`3`	`+/**`
	`4`	`+ * Program to implement Kadane’s Algorithm to`
	`5`	`+ * calculate maximum contiguous subarray sum of an array`
	`6`	`+ * Time Complexity: O(n)`
	`7`	`+ *`
	`8`	`+ * @author Nishita Aggarwal`
	`9`	`+ *`
	`10`	`+ */`
	`11`	`+`
	`12`	`+publicclassKadaneAlgorithm {`
	`13`	`+`
	`14`	`+/**`
	`15`	`+* This method implements Kadane's Algorithm`
	`16`	`+*`
	`17`	`+ * @param arr The input array`
	`18`	`+* @return The maximum contiguous subarray sum of the array`
	`19`	`+ *`
	`20`	`+ */`
	`21`	`+staticintlargestContiguousSum(intarr[]){`
	`22`	`+inti,len=arr.length,cursum=0,maxsum=Integer.MIN_VALUE;`
	`23`	`+if(len==0)//empty array`
	`24`	`+return0;`
	`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;`
	`35`	`+}`
	`36`	`+`
	`37`	`+/**`
	`38`	`+ * Main method`
	`39`	`+ *`
	`40`	`+ * @param args Command line arguments`
	`41`	`+ */`
	`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`	`+`
	`55`	`+}`

Comments

(0)