Maximum Subarray Sum After Multiplier | Leetcode 3976

// Solution-1: TC: O(N), SC: O(N)
class Solution {
    #define ll long long

    ll transform(const int& ele,const int& k,const bool is_positive){
        if(is_positive)
            return 1LL*ele*k;
        return ele>=0? floor(ele/k) : ceil(ele/k);
    }

    ll maxSumSubarray(vector<int>& nums,const int& k,const bool is_positive){
        int n = nums.size();
        vector<ll> no_trans(n),curr_trans(n),ended_trans(n);
        
        // Tracking 3 states as:
        // no_trans[i] = maxSumSubarray ending at 'i' without using any transformation
        // curr_trans[i] = maxSumSubarray ending at 'i' using transformation which ends at 'i'
        // ended_trans[i] = maxSumSubarray ending at 'i' using already ended transformation at j where j<i
    
        no_trans[0] = nums[0];
        curr_trans[0] = transform(nums[0],k,is_positive);
        ended_trans[0] = LLONG_MIN/8; //Impossible to have already ended transformation in the past

        //Fill states for all indices
        for(int i=1;i<n;++i){
            ll transformed_curr = transform(nums[i],k,is_positive);

            no_trans[i] = max<ll>(no_trans[i-1]+nums[i],nums[i]);
            curr_trans[i] = max<ll>({no_trans[i-1]+transformed_curr,curr_trans[i-1]+transformed_curr,transformed_curr});
            ended_trans[i] = max<ll>({curr_trans[i-1]+nums[i],ended_trans[i-1]+nums[i]});
        }

        ll max_sum = LLONG_MIN/8;
        for(int i=0;i<n;++i)
            max_sum = max<ll>({max_sum,curr_trans[i],ended_trans[i]});
        
        return max_sum;
    }
public:
    long long maxSubarraySum(vector<int>& nums, int k) {
        return max(maxSumSubarray(nums,k,true),maxSumSubarray(nums,k,false));
    }
};

// Solution-2: TC: O(N), SC: O(1)
class Solution {
    #define ll long long

    ll transform(const int& ele,const int& k,const bool is_positive){
        if(is_positive)
            return 1LL*ele*k;
        return ele>=0 ? floor(ele/k) : ceil(ele/k);
    }

    ll maxSumSubarray(vector<int>& nums,const int& k,const bool is_positive){
        int n = nums.size();

        ll no_trans, curr_trans, ended_trans;
        
        // Tracking 3 states as:
        // no_trans[i] = maxSumSubarray ending at 'i' without using any transformation
        // curr_trans[i] = maxSumSubarray ending at 'i' using transformation which ends at 'i'
        // ended_trans[i] = maxSumSubarray ending at 'i' using already ended transformation at j where j<i
    

        no_trans = nums[0];
        curr_trans = transform(nums[0],k,is_positive);
        ended_trans = LLONG_MIN/8; //Impossible to have already ended transformation in the past

        ll max_sum = max(curr_trans, ended_trans);

        //Fill states for all indices
        for(int i=1;i<n;++i){
            ll transformed_curr = transform(nums[i],k,is_positive);

            ll prev_no_trans = no_trans;
            ll prev_curr_trans = curr_trans;
            ll prev_ended_trans = ended_trans;

            no_trans = max<ll>(prev_no_trans + nums[i], nums[i]);
            curr_trans = max<ll>({
                prev_no_trans + transformed_curr,
                prev_curr_trans + transformed_curr,
                transformed_curr
            });
            ended_trans = max<ll>({
                prev_curr_trans + nums[i],
                prev_ended_trans + nums[i]
            });

            max_sum = max<ll>({max_sum, curr_trans, ended_trans});
        }

        return max_sum;
    }

public:
    long long maxSubarraySum(vector<int>& nums, int k) {
        return max(maxSumSubarray(nums,k,true),maxSumSubarray(nums,k,false));
    }
};

/*
//JAVA
//Solution-1: TC: O(N), SC: O(N)
class Solution {

    private long transform(int ele, int k, boolean is_positive) {
        if (is_positive)
            return 1L * ele * k;
        return ele >= 0 ? ele / k : -((-ele) / k);
    }

    private long maxSumSubarray(int[] nums, int k, boolean is_positive) {
        int n = nums.length;

        long[] no_trans = new long[n];
        long[] curr_trans = new long[n];
        long[] ended_trans = new long[n];

        
        // Tracking 3 states as:
        // no_trans[i] = maxSumSubarray ending at 'i' without using any transformation
        // curr_trans[i] = maxSumSubarray ending at 'i' using transformation which ends at 'i'
        // ended_trans[i] = maxSumSubarray ending at 'i' using already ended transformation at j where j<i
    

        no_trans[0] = nums[0];
        curr_trans[0] = transform(nums[0], k, is_positive);
        ended_trans[0] = Long.MIN_VALUE / 8;

        for (int i = 1; i < n; i++) {
            long transformed_curr = transform(nums[i], k, is_positive);

            no_trans[i] = Math.max(no_trans[i - 1] + nums[i], nums[i]);

            curr_trans[i] = Math.max(
                    transformed_curr,
                    Math.max(
                            no_trans[i - 1] + transformed_curr,
                            curr_trans[i - 1] + transformed_curr
                    )
            );

            ended_trans[i] = Math.max(
                    curr_trans[i - 1] + nums[i],
                    ended_trans[i - 1] + nums[i]
            );
        }

        long max_sum = Long.MIN_VALUE / 8;
        for (int i = 0; i < n; i++)
            max_sum = Math.max(max_sum, Math.max(curr_trans[i], ended_trans[i]));

        return max_sum;
    }

    public long maxSubarraySum(int[] nums, int k) {
        return Math.max(
                maxSumSubarray(nums, k, true),
                maxSumSubarray(nums, k, false)
        );
    }
}

//JAVA
//Solution-2: TC: O(N), SC: O(1)
class Solution {

    private long transform(int ele, int k, boolean is_positive) {
        if (is_positive)
            return 1L * ele * k;
        return ele >= 0 ? ele / k : -((-ele) / k);
    }

    private long maxSumSubarray(int[] nums, int k, boolean is_positive) {
        int n = nums.length;

        long no_trans, curr_trans, ended_trans;

        
        // Tracking 3 states as:
        // no_trans[i] = maxSumSubarray ending at 'i' without using any transformation
        // curr_trans[i] = maxSumSubarray ending at 'i' using transformation which ends at 'i'
        // ended_trans[i] = maxSumSubarray ending at 'i' using already ended transformation at j where j<i
        

        no_trans = nums[0];
        curr_trans = transform(nums[0], k, is_positive);
        ended_trans = Long.MIN_VALUE / 8;

        long max_sum = Math.max(curr_trans, ended_trans);

        for (int i = 1; i < n; i++) {
            long transformed_curr = transform(nums[i], k, is_positive);

            long prev_no_trans = no_trans;
            long prev_curr_trans = curr_trans;
            long prev_ended_trans = ended_trans;

            no_trans = Math.max(prev_no_trans + nums[i], nums[i]);

            curr_trans = Math.max(
                    transformed_curr,
                    Math.max(
                            prev_no_trans + transformed_curr,
                            prev_curr_trans + transformed_curr
                    )
            );

            ended_trans = Math.max(
                    prev_curr_trans + nums[i],
                    prev_ended_trans + nums[i]
            );

            max_sum = Math.max(max_sum, Math.max(curr_trans, ended_trans));
        }

        return max_sum;
    }

    public long maxSubarraySum(int[] nums, int k) {
        return Math.max(
                maxSumSubarray(nums, k, true),
                maxSumSubarray(nums, k, false)
        );
    }
*/
/*
#python
#Solution-1: TC: O(N), SC: O(N)

class Solution:
    def transform(self, ele, k, is_positive):
        if is_positive:
            return ele * k
        return ele // k if ele >= 0 else -((-ele) // k)

    def maxSumSubarray(self, nums, k, is_positive):
        n = len(nums)

        no_trans = [0] * n
        curr_trans = [0] * n
        ended_trans = [0] * n

        """
            Tracking 3 states as:
            no_trans[i] = maxSumSubarray ending at 'i' without using any transformation
            curr_trans[i] = maxSumSubarray ending at 'i' using transformation which ends at 'i'
            ended_trans[i] = maxSumSubarray ending at 'i' using already ended transformation at j where j<i
        """

        INF = float('-inf')

        no_trans[0] = nums[0]
        curr_trans[0] = self.transform(nums[0], k, is_positive)
        ended_trans[0] = INF

        for i in range(1, n):
            transformed_curr = self.transform(nums[i], k, is_positive)

            no_trans[i] = max(no_trans[i - 1] + nums[i], nums[i])

            curr_trans[i] = max(
                transformed_curr,
                no_trans[i - 1] + transformed_curr,
                curr_trans[i - 1] + transformed_curr,
            )

            ended_trans[i] = max(
                curr_trans[i - 1] + nums[i],
                ended_trans[i - 1] + nums[i],
            )

        max_sum = INF
        for i in range(n):
            max_sum = max(max_sum, curr_trans[i], ended_trans[i])

        return max_sum

    def maxSubarraySum(self, nums, k):
        return max(
            self.maxSumSubarray(nums, k, True),
            self.maxSumSubarray(nums, k, False),
        )

#Python
Solution-2: TC: O(N), SC: O(1)
class Solution:
    def transform(self, ele, k, is_positive):
        if is_positive:
            return ele * k
        return ele // k if ele >= 0 else -((-ele) // k)

    def maxSumSubarray(self, nums, k, is_positive):
        n = len(nums)

        """
            Tracking 3 states as:
            no_trans[i] = maxSumSubarray ending at 'i' without using any transformation
            curr_trans[i] = maxSumSubarray ending at 'i' using transformation which ends at 'i'
            ended_trans[i] = maxSumSubarray ending at 'i' using already ended transformation at j where j<i
        """

        INF = float('-inf')

        no_trans = nums[0]
        curr_trans = self.transform(nums[0], k, is_positive)
        ended_trans = INF

        max_sum = max(curr_trans, ended_trans)

        for i in range(1, n):
            transformed_curr = self.transform(nums[i], k, is_positive)

            prev_no_trans = no_trans
            prev_curr_trans = curr_trans
            prev_ended_trans = ended_trans

            no_trans = max(prev_no_trans + nums[i], nums[i])

            curr_trans = max(
                transformed_curr,
                prev_no_trans + transformed_curr,
                prev_curr_trans + transformed_curr,
            )

            ended_trans = max(
                prev_curr_trans + nums[i],
                prev_ended_trans + nums[i],
            )

            max_sum = max(max_sum, curr_trans, ended_trans)

        return max_sum

    def maxSubarraySum(self, nums, k):
        return max(
            self.maxSumSubarray(nums, k, True),
            self.maxSumSubarray(nums, k, False),
        )
*/