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 mx = ranges::max(milestones);
    const long sum = accumulate(milestones.begin(), milestones.end(), 0L);
    const long nonMax = sum - mx;
    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 mx = Arrays.stream(milestones).max().getAsInt();
    final long sum = Arrays.stream(milestones).asLongStream().sum();
    final long nonMax = sum - mx;
    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)