Welcome to Subscribe On Youtube

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:

  1. Multiply each number in the chosen subarray by k.
  2. 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 <= 105
  • -105 <= nums[i] <= 105
  • 1 <= k <= 105

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}$.

  • 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;
    }
};

  • 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


  • 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;
}

All Problems

All Solutions