Problem of The Day: Rearrange Array to Maximize Prefix Score

1 min read 380 words

Problem Statement

leetcode problem link

Solution [TLE]

class Solution:
    from itertools import permutations
    def maxScore(self, nums: List[int]) -> int:
        perm = permutations(nums)
        res = 0
        for p in perm:
            curr = 0
            pos = 0
            for x in p:
                curr += x
                if curr > 0:
                    pos += 1
            res = max(res, pos)

        return res

Solution [Accepted]

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        sorted_nums = sorted(nums, key=lambda x: -x)
        curr = 0
        res = 0
        for x in sorted_nums:
            curr += x
            if curr > 0:
                res += 1
        return res

using System;
using System.Linq;

public class Solution
{
    public int MaxScore(int[] nums)
    {
        var sortedNums = nums.OrderByDescending(x => x).ToArray();

        long prefixSum = 0; // use long to avoid overflow on large inputs
        int result = 0;

        foreach (var num in sortedNums)
        {
            prefixSum += num;
            if (prefixSum > 0)
            {
                result++;
            }
            else
            {
                break; // no more positives possible after this point
            }
        }

        return result;
    }
}