2560. House Robber IV Medium

1/**
2 * [2560] House Robber IV
3 *
4 * There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he refuses to steal from adjacent homes.
5 * The capability of the robber is the maximum amount of money he steals from one house of all the houses he robbed.
6 * You are given an integer array nums representing how much money is stashed in each house. More formally, the i^th house from the left has nums[i] dollars.
7 * You are also given an integer k, representing the minimum number of houses the robber will steal from. It is always possible to steal at least k houses.
8 * Return the minimum capability of the robber out of all the possible ways to steal at least k houses.
9 *  
10 * <strong class="example">Example 1:
11 * 
12 * Input: nums = [2,3,5,9], k = 2
13 * Output: 5
14 * Explanation: 
15 * There are three ways to rob at least 2 houses:
16 * - Rob the houses at indices 0 and 2. Capability is max(nums[0], nums[2]) = 5.
17 * - Rob the houses at indices 0 and 3. Capability is max(nums[0], nums[3]) = 9.
18 * - Rob the houses at indices 1 and 3. Capability is max(nums[1], nums[3]) = 9.
19 * Therefore, we return min(5, 9, 9) = 5.
20 * 
21 * <strong class="example">Example 2:
22 * 
23 * Input: nums = [2,7,9,3,1], k = 2
24 * Output: 2
25 * Explanation: There are 7 ways to rob the houses. The way which leads to minimum capability is to rob the house at index 0 and 4. Return max(nums[0], nums[4]) = 2.
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	1 <= nums.length <= 10^5
31 * 	1 <= nums[i] <= 10^9
32 * 	1 <= k <= (nums.length + 1)/2
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/house-robber-iv/
38// discuss: https://leetcode.com/problems/house-robber-iv/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42impl Solution {
43    pub fn min_capability(nums: Vec<i32>, k: i32) -> i32 {
44        0
45    }
46}
47
48// submission codes end
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53
54    #[test]
55    fn test_2560() {
56    }
57}
58