LC410. Split Array Largest Sum

class Solution:
    def splitArray0(self, nums: List[int], m: int) -> int:
        """  tc O(M*N*N) sc O(M*N)
        
        
        dp[i][j] : min val for j elements to split into i subarray, among their bigest subarray sum 
        dp[0][0] = 0
        dp[1][j] = A[0] + A[1] + ... + A[j-1]
        dp[2][j] = min(dp[2][j],max(dp[1][k],dp[2-1][j-k])
        dp[i][j] = min(dp[i][j],max(dp[1][j]-dp[1][k],dp[i-1][k]) ???
        
        """
        n = len(nums)
        dp = [ [0]*(n+1) for _ in range(m+1)]
        #print(len(dp),len(dp[0]))
        # base case 
        for i in range(n):
            dp[1][i+1] = dp[1][i] + nums[i]
        
        
        # dp[i][j] = min(dp[i][j], dp[i-1][k] + sum(num[k+1]... nums[j]) k -> i~j-1 )
        #  sum(num[k+1]... nums[j]) k -> i~j-1   ==> dp[1][j] - dp[1][k]
        for i in range(2,m+1):
            for j in range(i,n+1):
                dp[i][j] = float('inf')
                for k in range(i-1,j):
                    dp[i][j] = min(dp[i][j],max(dp[1][j]-dp[1][k] , dp[i-1][k]))
        return dp[m][n]
    

    def splitArray1(self, A: List[int], m: int) -> int:
        """ tc O(M*N^2)  sc O(N)
        """
        n = len(A)
        dp = [[0]*(n+1) for _ in range(3)]
        # base case 
        for i in range(n):
            dp[1][i+1] = dp[1][i] + A[i]
            dp[2][i+1] = dp[2][i] + A[i]
        """
        dp[i][j] = min(dp[i-1][k] + sum( nums[k] +  .. + nums[j-1])   k -> i~ j-1
        
        """
        for i in range(2,m+1):
            for j in range(i,n+1):
                dp[i%2][j] = float('inf')
                for k in range(i-1,j):
                    dp[i%2][j] = min(dp[i%2][j],max(dp[(i-1)%2][k],dp[2][j]-dp[2][k]))
        return dp[m%2][n]

class Solution:
    def splitArray(self, A: List[int], m: int) -> int:
        n = len(A)
        psum = [0]*(n+1)
        for i in range(n):
            psum[i+1] = psum[i]+A[i]
        #dp[i] definition:  best result to split A[i:] into  m groups 
        # dp[i]: sum of A[i] ~ A[n-1]
        dp = [0] *n 
        
        # base case when m == 1 
        for i in range(n):
            dp[i] = psum[n]- psum[i] # A[i] ~A[n-1]
        
        
        for i in range(2,m+1): # seperate into i sub groups
            # optimize: if there are i groups, there at least has i elements 
            for j in range(n-i+1):  # last subgroup total sum 
                # optimize if k >= n-i+2, dp[k] must be zero since its length <= i-2==> so make a upperbound 
                for k in range(j+1,n-i+2):
                    #         |<-sum[j-k]->|<-dp[k]->|  
                    #   xxxxxx|xxxxxxxxxxxx|xxxxxxxx
                    #        j             k 
                    t = max(dp[k],psum[k]-psum[j]) # sum(A[j:k])
                    # keep finding a smaller value until t is the smallest
                    if t <= dp[j]:
                    # dp[k] is decreasing since psum[k]-psum[j] is increasing if candidates become invalid, it will never be valid again
                    # without optmization. TLE
                        dp[j] =t 
                    else:
                        break
        return dp[0]
                

    class Solution:
    def splitArray(self, A: List[int], m: int) -> int:
        """ 
        tc O(Nlg(sum(A)))  sc O(1)
       1. initialization: get max num and sum 
       2. set left,right ptr as max num and sum 
       3. within [max num , sum ] do binary search find largest subarray as mid, count number of valid subarry 
       4. adjust left, right ptr until mid is found 
        note, this binary search approach won't work if there are negtive numbers in the array 
        """
        max_a = total = 0
        for a in A:
            max_a = max(a,max_a)
            total += a 
        l,r = max_a, total +1 # note here right boundry +1 
        while l < r :
# max subarray sum is mid, every subarray once reached to mid will be splited into another subarray            
            mid = l+(r-l)//2
            sub_sum = 0
            cnt = 1 # here initialize = 1 not  0
            for i in range(len(A)):
                if A[i] + sub_sum > mid:
                    sub_sum = A[i]
                    cnt += 1  # track number of subar
                else:
                    sub_sum += A[i]
            if cnt > m: # left ptr to mid+1 
                l = mid + 1
            else:
                r = mid # keep close towards largest mid value 
        return r # or l