3976. Maximum Subarray Sum After Multiplier

Description

You are given an integer array nums and a positive integer k.

You must choose exactly one subarray of nums and perform exactly one of the following operations:

Multiply each number in the chosen subarray by k.
Divide each number in the chosen subarray by k.
- When dividing a positive number by k, use the floor value of the division result.
- When dividing a negative number by k, use the ceiling value of the division result.

Return the maximum possible sum of a non-empty subarray in the resulting array.

Note that the subarray chosen for the operation and the subarray chosen for the sum may be different.

Example 1:

Input: nums = [1,-2,3,4,-5], k = 2

Output: 14

Explanation:

Multiply each number in the subarray [3, 4] by 2.
This results in nums = [1, -2, 6, 8, -5].
The subarray with the largest sum is [6, 8], so the output is 6 + 8 = 14.

Example 2:

Input: nums = [-5,-4,-3], k = 2

Output: -1

Explanation:

Divide each number in the subarray [-3] by 2.
This results in nums = [-5, -4, -1].
The subarray with the largest sum is [-1], so the output is -1.

Constraints:

1 <= nums.length <= 10⁵
-10⁵ <= nums[i] <= 10⁵
1 <= k <= 10⁵

Solutions

Solution 1: Dynamic Programming

We define \(f[i][j]\) as the maximum subarray sum ending at \(nums[i]\) with current state \(j\). There are \(4\) states for \(j\):

State \(0\): the current subarray has not undergone any operation yet;
State \(1\): the current subarray is being multiplied by \(k\);
State \(2\): the current subarray is being divided by \(k\);
State \(3\): the operation on the current subarray has been completed.

Initially, \(f[0][0] = 0\), and all other \(f[i][j] = -\infty\).

Next, we consider the state transitions. For the \(i\)-th number \(nums[i]\), we can choose not to perform any operation, multiply by \(k\), divide by \(k\), or continue after the operation has been completed:

If we perform no operation, then \(f[i][0] = \max(f[i-1][0], 0) + nums[i]\);
If we multiply by \(k\), then \(f[i][1] = \max(f[i-1][0], f[i-1][1], 0) + nums[i] \times k\);
If we divide by \(k\), then \(f[i][2] = \max(f[i-1][0], f[i-1][2], 0) + \lfloor \frac{nums[i]}{k} \rfloor\);
If the operation has been completed, then \(f[i][3] = \max(f[i-1][1], f[i-1][2], f[i-1][3]) + nums[i]\).

We take the maximum among all states as the answer.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(\textit{nums}\).

Python3JavaC++GoTypeScript

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [[-inf] * 4 for _ in range(n + 1)]
        f[0][0] = 0
        ans = -inf
        for i, x in enumerate(nums, 1):
            f[i][0] = max(f[i - 1][0], 0) + x
            f[i][1] = max(f[i - 1][0], f[i - 1][1], 0) + x * k
            f[i][2] = max(f[i - 1][0], f[i - 1][2], 0) + int(x / k)
            f[i][3] = max(f[i - 1][1], f[i - 1][2], f[i - 1][3]) + x
            ans = max(ans, max(f[i]))
        return ans

class Solution {
    public long maxSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long inf = Long.MIN_VALUE / 4;

        long[][] f = new long[n + 1][4];

        for (int i = 0; i <= n; i++) {
            Arrays.fill(f[i], inf);
        }

        f[0][0] = 0;
        long ans = inf;

        for (int i = 1; i <= n; i++) {
            long x = nums[i - 1];

            f[i][0] = Math.max(f[i - 1][0], 0) + x;
            f[i][1] = Math.max(Math.max(f[i - 1][0], f[i - 1][1]), 0) + x * k;
            f[i][2] = Math.max(Math.max(f[i - 1][0], f[i - 1][2]), 0) + (x / k);
            f[i][3] = Math.max(Math.max(f[i - 1][1], f[i - 1][2]), f[i - 1][3]) + x;

            ans = Math.max(ans, Math.max(Math.max(f[i][0], f[i][1]), Math.max(f[i][2], f[i][3])));
        }

        return ans;
    }
}

class Solution {
public:
    long long maxSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        long long inf = numeric_limits<long long>::min() / 4;

        vector<array<long long, 4>> f(n + 1);

        for (int i = 0; i <= n; i++) {
            f[i].fill(inf);
        }

        f[0][0] = 0;
        long long ans = inf;

        for (int i = 1; i <= n; i++) {
            long long x = nums[i - 1];

            f[i][0] = max(f[i - 1][0], 0LL) + x;
            f[i][1] = max({f[i - 1][0], f[i - 1][1], 0LL}) + x * k;
            f[i][2] = max({f[i - 1][0], f[i - 1][2], 0LL}) + (x / k);
            f[i][3] = max({f[i - 1][1], f[i - 1][2], f[i - 1][3]}) + x;

            ans = max(ans, *max_element(f[i].begin(), f[i].end()));
        }

        return ans;
    }
};

func maxSubarraySum(nums []int, k int) int64 {
    n := len(nums)
    inf := int64(math.MinInt64 / 4)

    f := make([][4]int64, n+1)
    for i := range f {
        for j := 0; j < 4; j++ {
            f[i][j] = inf
        }
    }

    f[0][0] = 0
    ans := inf

    for i := 1; i <= n; i++ {
        x := int64(nums[i-1])

        f[i][0] = max(f[i-1][0], 0) + x
        f[i][1] = max(max(f[i-1][0], f[i-1][1]), 0) + x*int64(k)
        f[i][2] = max(max(f[i-1][0], f[i-1][2]), 0) + x/int64(k)
        f[i][3] = max(max(f[i-1][1], f[i-1][2]), f[i-1][3]) + x

        ans = max(ans, max(max(f[i][0], f[i][1]), max(f[i][2], f[i][3])))
    }

    return ans
}

function maxSubarraySum(nums: number[], k: number): number {
    const n = nums.length;
    const inf = -1e18;

    const f: number[][] = Array.from({ length: n + 1 }, () => {
        const arr = new Array(4).fill(inf);
        return arr;
    });

    f[0][0] = 0;
    let ans = inf;

    for (let i = 1; i <= n; i++) {
        const x = nums[i - 1];

        f[i][0] = Math.max(f[i - 1][0], 0) + x;
        f[i][1] = Math.max(Math.max(f[i - 1][0], f[i - 1][1]), 0) + x * k;
        f[i][2] = Math.max(Math.max(f[i - 1][0], f[i - 1][2]), 0) + Math.trunc(x / k);
        f[i][3] = Math.max(Math.max(f[i - 1][1], f[i - 1][2]), f[i - 1][3]) + x;

        ans = Math.max(ans, Math.max(...f[i]));
    }

    return ans;
}

3976. Maximum Subarray Sum After Multiplier

Description

Solutions

Solution 1: Dynamic Programming

Comments