Maximum difference of prefix sum for all indices of given two Arrays
Given 2 arrays of integers a[] and s[] both of size N. The task is to find the maximum difference of prefix sum for all indices of the given arrays.
Examples:
Input: N = 5, a[] = {20, 20, 35, 20, 35}, s[] = {21, 31, 34, 41, 14}
Output: 32
Explanation: After prefix sum the arrays are a[] = {20, 40, 75, 95, 130}
and b[] = {21, 52, 86, 127, 141} for S. The maximum difference is (127 – 95) = 32 for 4th position.Input: N = 1, a[] = {32}, s[] = {15}
Output: A, 17
Explanation: The highest difference (since only one element) is 32 – 15 = 17.
Approach: This problem can be solved by calculating the prefix sum in both the arrays and then comparing the differences for every index. Follow the steps below to solve the problem:
- Iterate over the range [0, n) using the variable i and calculate the prefix sum for both the arrays.
- Calculate the difference of prefix sum for every index.
- Return the maximum difference.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to get the winner int getWinner( int a[], int s[], int N) { int maxDiff = abs (a[0] - s[0]); // Calculating prefix sum for ( int i = 1; i < N; i++) { a[i] += a[i - 1]; s[i] += s[i - 1]; maxDiff = max(maxDiff, abs (a[i] - s[i])); } // Return the result return maxDiff; } // Driver Code int main() { int N = 5; int a[] = { 20, 20, 35, 20, 35 }, s[] = { 21, 31, 34, 41, 14 }; cout << getWinner(a, s, N); return 0; } |
Java
// Java program for the above approach class GFG{ // Function to get the winner static int getWinner( int a[], int s[], int N) { int maxDiff = Math.abs(a[ 0 ] - s[ 0 ]); // Calculating prefix sum for ( int i = 1 ; i < N; i++) { a[i] += a[i - 1 ]; s[i] += s[i - 1 ]; maxDiff = Math.max(maxDiff, Math.abs(a[i] - s[i])); } // Return the result return maxDiff; } // Driver Code public static void main(String[] args) { int N = 5 ; int a[] = { 20 , 20 , 35 , 20 , 35 }, s[] = { 21 , 31 , 34 , 41 , 14 }; System.out.print(getWinner(a, s, N)); } } // This code is contributed by Rajput-Ji |
Python3
# python3 program for the above approach # Function to get the winner def getWinner(a, s, N): maxDiff = abs (a[ 0 ] - s[ 0 ]) # Calculating prefix sum for i in range ( 1 , N): a[i] + = a[i - 1 ] s[i] + = s[i - 1 ] maxDiff = max (maxDiff, abs (a[i] - s[i])) # Return the result return maxDiff # Driver Code if __name__ = = "__main__" : N = 5 a = [ 20 , 20 , 35 , 20 , 35 ] s = [ 21 , 31 , 34 , 41 , 14 ] print (getWinner(a, s, N)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; class GFG { // Function to get the winner static int getWinner( int [] a, int [] s, int N) { int maxDiff = Math.Abs(a[0] - s[0]); // Calculating prefix sum for ( int i = 1; i < N; i++) { a[i] += a[i - 1]; s[i] += s[i - 1]; maxDiff = Math.Max(maxDiff, Math.Abs(a[i] - s[i])); } // Return the result return maxDiff; } // Driver Code public static void Main( string [] args) { int N = 5; int [] a = { 20, 20, 35, 20, 35 }; int [] s = { 21, 31, 34, 41, 14 }; Console.WriteLine(getWinner(a, s, N)); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function to get the winner function getWinner(a, s, N) { let maxDiff = Math.abs(a[0] - s[0]); // Calculating prefix sum for (let i = 1; i < N; i++) { a[i] += a[i - 1]; s[i] += s[i - 1]; maxDiff = Math.max(maxDiff, Math.abs(a[i] - s[i])); } // Return the result return maxDiff; } // Driver Code let N = 5; let a = [20, 20, 35, 20, 35], s = [21, 31, 34, 41, 14]; document.write(getWinner(a, s, N)); // This code is contributed by Potta Lokesh </script> |
32
Time Complexity: O(N)
Auxiliary Space: O(1)