Skip to content

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<int>& 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)