1191. K-Concatenation Maximum Sum

Link

Solution

找出一個串列的case下的maximum

    public long findMaxSum(int[] arr){
        long max = Integer.MIN_VALUE;
        long curMaxSum = 0;
        for(int i = 0; i < arr.length ; i++){
            curMaxSum = curMaxSum > 0 ? (curMaxSum + arr[i])%mod : arr[i];
            max = Math.max(max, curMaxSum);
        }
        return max > 0 ? max : 0;
    }
    

找出prefix的Maximun

     public long findPrefixMax(int[] arr){
        long currentSum=0;
        long maxSum=Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++){
            currentSum = (currentSum+arr[i])%mod;
            maxSum=Math.max(maxSum,currentSum);
        }
        return maxSum;
    }

找出Suffix的Maximun

  
     public long findSuffixMax(int[] arr){
        long currentSum=0;
        long maxSum=Integer.MIN_VALUE;
        for(int i=arr.length-1;i>=0;i--){
            currentSum =(currentSum+arr[i])%mod;
            maxSum=Math.max(currentSum,maxSum);
        }
        return maxSum;
    }

最後結果是 sum*(k-2) + prefix + suffix, if sum > 0

或者是 sum < 0 : prefix + suffix

    int mod = (int)(1e9 + 7);
    public int kConcatenationMaxSum(int[] arr, int k) {
        long oneMax = findMaxSum(arr);
        if( k == 1) return (int)oneMax;
        
        long preMax = findPreMax(arr);
        long suffixMax = findSuffixMax(arr);
        long sum = 0;
        for(int num : arr){
            sum += num;
        }
        int ret = Integer.MIN_VALUE;
        if(sum > 0){
            ret = (int)Math.max((preMax + suffixMax + ((sum*(k-2))%mod))%mod, oneMax);
        }else{
            ret = (int)Math.max((preMax + suffixMax)%mod, oneMax);
        }
        return ret;
    }
    
    public long findMaxSum(int[] arr){
        long max = Integer.MIN_VALUE;
        long curMaxSum = 0;
        for(int i = 0; i < arr.length ; i++){
            curMaxSum = curMaxSum > 0 ? (curMaxSum + arr[i])%mod : arr[i];
            max = Math.max(max, curMaxSum);
        }
        return max > 0 ? max : 0;
    }
    
    public long findPreMax(int[] arr){
        long currentSum=0;
        long maxSum=Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++){
            currentSum = (currentSum+arr[i])%mod;
            maxSum=Math.max(maxSum,currentSum);
        }
        return maxSum;
    }
    
     public long findSuffixMax(int[] arr){
        long currentSum=0;
        long maxSum=Integer.MIN_VALUE;
        for(int i=arr.length-1;i>=0;i--){
            currentSum =(currentSum+arr[i])%mod;
            maxSum=Math.max(currentSum,maxSum);
        }
        return maxSum;
    }