Commita49e1d1

Leyang Zou

authored

* Create _1402.cpp* Update README.md* Update README.md

1 parent466334e commita49e1d1Copy full SHA for a49e1d1

File tree

+20

-0

lines changed

+20

-0

lines changed

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -86,6 +86,7 @@ _If you like this project, please leave me a star._ ★`
`86`	`86`	`\|1409\|[Queries on a Permutation With Key](https://leetcode.com/problems/queries-on-a-permutation-with-key/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1409.java)\|\|Medium\|Array\|`
`87`	`87`	`\|1408\|[String Matching in an Array](https://leetcode.com/problems/string-matching-in-an-array/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1408.java)\|\|Easy\|String\|`
`88`	`88`	`\|1403\|[Minimum Subsequence in Non-Increasing Order](https://leetcode.com/problems/minimum-subsequence-in-non-increasing-order/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1403.java)\|\|Easy\|Greedy, Sort\|`
	`89`	`+\|1402\|[Reducing Dishes](https://leetcode.com/problems/reducing-dishes/)\|[Solution](../master/cpp/_1402.cpp)\|\|Hard\|Dynamic Programming\|`
`89`	`90`	`\|1401\|[Circle and Rectangle Overlapping](https://leetcode.com/problems/circle-and-rectangle-overlapping/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1401.java)\|\|Medium\|Geometry\|`
`90`	`91`	`\|1400\|[Construct K Palindrome Strings](https://leetcode.com/problems/construct-k-palindrome-strings/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1400.java)\|\|Medium\|Greedy\|`
`91`	`92`	`\|1399\|[Count Largest Group](https://leetcode.com/problems/count-largest-group/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1399.java)\|\|Easy\|Array\|`

Lines changed: 19 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,19 @@`
	`1`	`+classSolution {`
	`2`	`+public:`
	`3`	`+intmaxSatisfaction(vector<int>& sat) {`
	`4`	`+// we'll greedily only consider a suffix of the sorted array`
	`5`	`+sort(sat.begin(), sat.end());`
	`6`	`+int cmax =0;`
	`7`	`+int sum =0;`
	`8`	`+int csum =0;`
	`9`	`+int i = sat.size();// iterate from n - 1 to 0`
	`10`	`+while(i--) {`
	`11`	`+// calulate current satisfaction`
	`12`	`+ csum += sat[i];`
	`13`	`+ sum += csum;`
	`14`	`+// compare with cmax`
	`15`	`+ cmax =max(cmax, sum);`
	`16`	`+ }`
	`17`	`+return cmax;`
	`18`	`+ }`
	`19`	`+};`

Comments

(0)