Commit985f821

authored

Merge pull requestneetcode-gh#3097 from bitscoder/main

Create: 2140-solving-questions-with-brainpower.cpp

2 parentsed2bdc1 +74cbcd7 commit985f821Copy full SHA for 985f821

File tree

+28

-0

lines changed

+28

-0

lines changed

Lines changed: 28 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,28 @@`
	`1`	`+// Time Complexity: O(n)`
	`2`	`+// Space Complexity: O(n)`
	`3`	`+`
	`4`	`+classSolution`
	`5`	`+{`
	`6`	`+public:`
	`7`	`+longlongmostPoints(vector<vector<int>> &questions)`
	`8`	`+ {`
	`9`	`+int n = questions.size();`
	`10`	`+ vector<longlong>dp(n,0);`
	`11`	`+ dp[n -1] = questions[n -1][0];`
	`12`	`+longlong ans = dp[n -1];`
	`13`	`+for (int i = n -2; i >=0; i--)`
	`14`	`+ {`
	`15`	`+int k = i + questions[i][1] +1;`
	`16`	`+if (k < n)`
	`17`	`+ {`
	`18`	`+ dp[i] = (dp[k] + questions[i][0]) > dp[i +1] ? (dp[k] + questions[i][0]) : dp[i +1];`
	`19`	`+ }`
	`20`	`+else`
	`21`	`+ {`
	`22`	`+ dp[i] = questions[i][0] > dp[i +1] ? questions[i][0] : dp[i +1];`
	`23`	`+ }`
	`24`	`+ ans = ans > dp[i] ? ans : dp[i];`
	`25`	`+ }`
	`26`	`+return ans;`
	`27`	`+ }`
	`28`	`+};`

Comments

(0)