1953. Maximum Number of Weeks for Which You Can Work

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 class Solution { public: long long numberOfWeeks(vector& milestones) { // The best strategy is to pick "max, nonMax, max, nonMax, ...". const int max = *max_element(begin(milestones), end(milestones)); const long long sum = accumulate(begin(milestones), end(milestones), 0LL); const long long nonMax = sum - max; return min(sum, 2 * nonMax + 1); } }; 
 1 2 3 4 5 6 7 8 9 class Solution { public long numberOfWeeks(int[] milestones) { // The best strategy is to pick "max, nonMax, max, nonMax, ...". final int max = Arrays.stream(milestones).max().getAsInt(); final long sum = Arrays.stream(milestones).asLongStream().sum(); final long nonMax = sum - max; return Math.min(sum, 2 * nonMax + 1); } } 
 1 2 3 4 5 6 class Solution: def numberOfWeeks(self, milestones: List[int]) -> int: # The best strategy is to pick 'max, nonMax, max, nonMax, ...'. summ = sum(milestones) nonMax = summ - max(milestones) return min(summ, 2 * nonMax + 1)