# 15.02.2024 [2971. Find Polygon With the Largest Perimeter]
The largest subset sum(a[..i]) > a[i + 1] where a is a subset of array.
15.02.2024
2971. Find Polygon With the Largest Perimeter medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/506
Problem TLDR
The largest subset sum(a[…i]) > a[i + 1] where a is a subset of array.
Intuition
First, understand the problem: [1,12,1,2,5,50,3]
doesn’t have a polygon, but [1,12,1,2,5,23,3]
does. After this, the solution is trivial: take numbers in increasing order, compare with sum and check.
Approach
Let’s try to use the languages.
Kotlin:
sorted
,fold
Rust:
sort_unstable
,iter
,fold
Complexity
Time complexity:
O(nlog(n))Space complexity:
O(1),sorted
takes O(n) but can be avoided
Code
fun largestPerimeter(nums: IntArray) = nums
.sorted()
.fold(0L to -1L) { (s, r), x ->
s + x to if (s > x) s + x else r
}.second
pub fn largest_perimeter(mut nums: Vec<i32>) -> i64 {
nums.sort_unstable();
nums.iter().fold((0, -1), |(s, r), &x|
(s + x as i64, if s > x as i64 { s + x as i64 } else { r })
).1
}