Commit 4a61970

authored

Merge pull request #4 from Megha1209/patch-2

Create lc673.java

2 parents ac351c1 + e07a109 commit 4a61970Copy full SHA for 4a61970

File tree

+36

-0

lines changed

+36

-0

lines changed

Lines changed: 36 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,36 @@`
	`1`	`+public static int findNumberOfLIS(int[] arr) {`
	`2`	`+ if(arr.length<=1) return arr.length;`
	`3`	`+`
	`4`	`+ int n=arr.length;`
	`5`	`+ int[] dp=new int[n];`
	`6`	`+ int[] count=new int[n];`
	`7`	`+`
	`8`	`+ int maxLen=0;`
	`9`	`+ int maxCount=0;`
	`10`	`+`
	`11`	`+ for(int i=0;i<n;i++){`
	`12`	`+ dp[i]=1;`
	`13`	`+ count[i]=1;`
	`14`	`+ for(int j=0;j<i;j++){`
	`15`	`+ if(arr[i]>arr[j]){`
	`16`	`+ if(dp[j] + 1 > dp[i]){`
	`17`	`+ dp[i]=dp[j]+1;`
	`18`	`+ count[i]=count[j];`
	`19`	`+ }else if(dp[j]+1==dp[i]){`
	`20`	`+ count[i]+=count[j];`
	`21`	`+ }`
	`22`	`+ }`
	`23`	`+ }`
	`24`	`+`
	`25`	`+ if(dp[i]>maxLen){`
	`26`	`+ maxLen=dp[i];`
	`27`	`+ maxCount=count[i];`
	`28`	`+ }else if(dp[i]==maxLen){`
	`29`	`+ maxCount+=count[i];`
	`30`	`+ }`
	`31`	`+ }`
	`32`	`+`
	`33`	`+ return maxCount;`
	`34`	`+`
	`35`	`+`
	`36`	`+ }`

Comments

(0)