Посты за 26 февраля 2023

TRILOGY SOLUTIONS GROUP : https://t.me/cod_solutions

public int solve(int[] A) {     int n = A.length;     int mod = 1000000007;     // calculate prefix sum and suffix sum arrays     long[] prefixSum = new long[n];     long[] suffixSum = new long[n];     prefixSum[0] = A[0];     suffixSum[n-1] = A[n-1];     for (int i = 1; i < n; i++) {         prefixSum[i] = prefixSum[i-1] + A[i];         suffixSum[n-1-i] = suffixSum[n-i] + A[n-1-i];     }     // calculate the maximum sum of one subarray from the left     long[] maxSumLeft = new long[n];     long curSum = 0;     long curMax = Long.MIN_VALUE;     for (int i = 0; i < n; i++) {         curSum += A[i];         curMax = Math.max(curMax, curSum);         maxSumLeft[i] = curMax;         curSum = Math.max(curSum, 0);     }     // calculate the maximum sum of one subarray from the right     long[] maxSumRight = new long[n];     curSum = 0;     curMax = Long.MIN_VALUE;     for (int i = n-1; i >= 0; i--) {         curSum += A[i];         curMax = Math.max(curMax, curSum);         maxSumRight[i] = curMax;         curSum = Math.max(curSum, 0);     }     // calculate the maximum sum of three subarrays     long maxSum = Long.MIN_VALUE;     for (int i = 1; i < n-1; i++) {         long sum1 = maxSumLeft[i-1];         long sum2 = maxSumRight[i+1];         long sum3 = prefixSum[i-1] + suffixSum[i+1];         maxSum = Math.max(maxSum, sum1+sum2+sum3);     }     return (int)(maxSum % mod); }

Three Subarray #Triology

In python def max_sum_subarrays(arr):     n = len(arr)     k = n // 3  # size of each window     mod = 10**3 + 7  # modulo value         # initialize windows     window1 = arr[:k]     window2 = arr[k:2*k]     window3 = arr[2*k:3*k]         # initialize sums     sum1 = sum(window1)     sum2 = sum(window2)     sum3 = sum(window3)         # iterate over the rest of the array and update windows and sums     for i in range(k, n-k):         sum1 += arr[i] - window1[i-k]         sum2 += arr[i+k] - window2[i-k]         sum3 += arr[i+2*k] - window3[i-k]                 # update windows         window1[i-k] = arr[i]         window2[i-k] = arr[i+k]         window3[i-k] = arr[i+2*k]                 # update maximum sums         sum1 = max(sum1, 0)         sum2 = max(sum2, 0)         sum3 = max(sum3, 0)         # return the positive remainder after dividing the sum with modulo value     return (sum1 + sum2 + sum3) % mod

Three Subarrays #Trilogy

public int solve(int[] A) {     int n = A.length;     int mod = 1000000007;     // calculate prefix sum and suffix sum arrays     long[] prefixSum = new long[n];     long[] suffixSum = new long[n];     prefixSum[0] = A[0];     suffixSum[n-1] = A[n-1];     for (int i = 1; i < n; i++) {         prefixSum[i] = prefixSum[i-1] + A[i];         suffixSum[n-1-i] = suffixSum[n-i] + A[n-1-i];     }     // calculate the maximum sum of one subarray from the left     long[] maxSumLeft = new long[n];     long curSum = 0;     long curMax = Long.MIN_VALUE;     for (int i = 0; i < n; i++) {         curSum += A[i];         curMax = Math.max(curMax, curSum);         maxSumLeft[i] = curMax;         curSum = Math.max(curSum, 0);     }     // calculate the maximum sum of one subarray from the right     long[] maxSumRight = new long[n];     curSum = 0;     curMax = Long.MIN_VALUE;     for (int i = n-1; i >= 0; i--) {         curSum += A[i];         curMax = Math.max(curMax, curSum);         maxSumRight[i] = curMax;         curSum = Math.max(curSum, 0);     }     // calculate the maximum sum of three subarrays     long maxSum = Long.MIN_VALUE;     for (int i = 1; i < n-1; i++) {         long sum1 = maxSumLeft[i-1];         long sum2 = maxSumRight[i+1];         long sum3 = prefixSum[i-1] + suffixSum[i+1];         maxSum = Math.max(maxSum, sum1+sum2+sum3);     }     return (int)(maxSum % mod); }