3976. Maximum Subarray Sum After Multiplier

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.

class Solution {
public:
    long long maxSubarraySum(vector<int>& nums, int k) {
        long long res = *max_element(begin(nums), end(nums)), n = nums.size();
        vector<long long> suf(n + 1);
        for(int i = n - 1; i >= 0; i--) {
            suf[i] = max(suf[i], suf[i+1] + nums[i]);
        }
        vector<long long> dp(3, 0);
        for(int i = 0; i < n; i++) {
            vector<long long> dpp(3, 0);
            dpp[0] = max(0ll,dp[0]) + nums[i];
            dpp[1] = max({0ll,dp[0], dp[1]}) + 1ll * nums[i] * k;
            dpp[2] = max({0ll,dp[0], dp[2]}) + 1ll * nums[i] / k;
            res = max(res, *max_element(begin(dpp), end(dpp)) + suf[i+1]);
            swap(dp,dpp);
        }
        return res;
    }
};