Commitdfecd2a

committed

Add C++ implementation

Signed-off-by: begeekmyfriend <begeekmyfriend@gmail.com>

1 parent018c984 commitdfecd2aCopy full SHA for dfecd2a

File tree

+68

-0

lines changed

+68

-0

lines changed

Lines changed: 2 additions & 0 deletions

Lines changed: 41 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,41 @@`
	`1`	`+#include<stdio.h>`
	`2`	`+#include<stdlib.h>`
	`3`	`+`
	`4`	`+`
	`5`	`+staticintbinary_search(int*nums,intlo,inthi,inttarget)`
	`6`	`+{`
	`7`	`+while (lo+1<hi) {`
	`8`	`+intmid=lo+ (hi-lo) /2;`
	`9`	`+if (nums[mid]<target) {`
	`10`	`+lo=mid;`
	`11`	`+ }else {`
	`12`	`+hi=mid;`
	`13`	`+ }`
	`14`	`+ }`
	`15`	`+returnhi;`
	`16`	`+}`
	`17`	`+`
	`18`	`+intlengthOfLIS(int*nums,intnumsSize){`
	`19`	`+inti,piles=0;`
	`20`	`+inttops=malloc(numsSizesizeof(int));`
	`21`	`+for (i=0;i<numsSize;i++) {`
	`22`	`+intpos=binary_search(tops,-1,piles,nums[i]);`
	`23`	`+if (pos==piles) {`
	`24`	`+piles++;`
	`25`	`+ }`
	`26`	`+tops[pos]=nums[i];`
	`27`	`+ }`
	`28`	`+returnpiles;`
	`29`	`+}`
	`30`	`+`
	`31`	`+intmain(intargc,char**argv)`
	`32`	`+{`
	`33`	`+inti;`
	`34`	`+intnums=malloc((argc-1)sizeof(int));`
	`35`	`+for (i=0;i<argc-1;i++) {`
	`36`	`+nums[i]=atoi(argv[i+1]);`
	`37`	`+ }`
	`38`	`+`
	`39`	`+printf("%d\n",lengthOfLIS(nums,argc-1));`
	`40`	`+return0;`
	`41`	`+}`

Lines changed: 25 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,25 @@`
	`1`	`+#include<bits/stdc++.h>`
	`2`	`+`
	`3`	`+usingnamespacestd;`
	`4`	`+`
	`5`	`+classSolution {`
	`6`	`+public:`
	`7`	`+intlengthOfLIS(vector<int>& nums) {`
	`8`	`+ vector<int>dp(nums.size(),1);`
	`9`	`+for (int i =0; i < nums.size(); i++) {`
	`10`	`+for (int j =0; j < i; j++) {`
	`11`	`+if (nums[j] < nums[i] && dp[j] +1 > dp[i]) {`
	`12`	`+ dp[i] = dp[j] +1;`
	`13`	`+ }`
	`14`	`+ }`
	`15`	`+ }`
	`16`	`+`
	`17`	`+int res =0;`
	`18`	`+for (int i : dp) {`
	`19`	`+if (i > res) {`
	`20`	`+ res = i;`
	`21`	`+ }`
	`22`	`+ }`
	`23`	`+return res;`
	`24`	`+ }`
	`25`	`+};`

Comments

(0)