Given two arrays, A[] and B[] each of length N where A[i] and B[i] are the prices of the ith item when sold in market A and market B respectively. The task is to maximize the profile of selling all the N items, but there is a catch: if you went to market B then you can not return. For example, if you sell the first k items in market A and you have to sell the rest of the items in market B.
Examples:
Input: A[] = {2, 3, 2}, B[] = {10, 3, 40}
Output: 53
Sell all the items in market B in order to
maximize the profit i.e. (10 + 3 + 40) = 53.Input: A[] = {7, 5, 3, 4}, B[] = {2, 3, 1, 3}
Output: 19
Approach:
- Create a prefix sum array preA[] where preA[i] will store the profit when the items A[0…i] are sold in market A.
- Create a suffix sum array suffB[] where suffB[i] will store the profit when item B[i…n-1] is sold in market B.
- Now the problem is reduced to finding an index i such that (preA[i] + suffB[i + 1]) is the maximum.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to calculate max profitint maxProfit(int profitA[], int profitB[], int n){ // Prefix sum array for profitA[] int preSum[n]; preSum[0] = profitA[0]; for (int i = 1; i < n; i++) { preSum[i] = preSum[i - 1] + profitA[i]; } // Suffix sum array for profitB[] int suffSum[n]; suffSum[n - 1] = profitB[n - 1]; for (int i = n - 2; i >= 0; i--) { suffSum[i] = suffSum[i + 1] + profitB[i]; } // If all the items are sold in market A int res = preSum[n - 1]; // Find the maximum profit when the first i // items are sold in market A and the // rest of the items are sold in market // B for all possible values of i for (int i = 1; i < n - 1; i++) { res = max(res, preSum[i] + suffSum[i + 1]); } // If all the items are sold in market B res = max(res, suffSum[0]); return res;}// Driver codeint main(){ int profitA[] = { 2, 3, 2 }; int profitB[] = { 10, 30, 40 }; int n = sizeof(profitA) / sizeof(int); // Function to calculate max profit cout << maxProfit(profitA, profitB, n); return 0;} |
Java
// Java implementation of the approach class GFG { // Function to calculate max profit static int maxProfit(int profitA[], int profitB[], int n) { // Prefix sum array for profitA[] int preSum[] = new int[n]; preSum[0] = profitA[0]; for (int i = 1; i < n; i++) { preSum[i] = preSum[i - 1] + profitA[i]; } // Suffix sum array for profitB[] int suffSum[] = new int[n]; suffSum[n - 1] = profitB[n - 1]; for (int i = n - 2; i >= 0; i--) { suffSum[i] = suffSum[i + 1] + profitB[i]; } // If all the items are sold in market A int res = preSum[n - 1]; // Find the maximum profit when the first i // items are sold in market A and the // rest of the items are sold in market // B for all possible values of i for (int i = 1; i < n - 1; i++) { res = Math.max(res, preSum[i] + suffSum[i + 1]); } // If all the items are sold in market B res = Math.max(res, suffSum[0]); return res; } // Driver code public static void main (String[] args) { int profitA[] = { 2, 3, 2 }; int profitB[] = { 10, 30, 40 }; int n = profitA.length; // Function to calculate max profit System.out.println(maxProfit(profitA, profitB, n)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to calculate max profit def maxProfit(profitA, profitB, n) : # Prefix sum array for profitA[] preSum = [0] * n; preSum[0] = profitA[0]; for i in range(1, n) : preSum[i] = preSum[i - 1] + profitA[i]; # Suffix sum array for profitB[] suffSum = [0] * n; suffSum[n - 1] = profitB[n - 1]; for i in range(n - 2, -1, -1) : suffSum[i] = suffSum[i + 1] + profitB[i]; # If all the items are sold in market A res = preSum[n - 1]; # Find the maximum profit when the first i # items are sold in market A and the # rest of the items are sold in market # B for all possible values of i for i in range(1 , n - 1) : res = max(res, preSum[i] + suffSum[i + 1]); # If all the items are sold in market B res = max(res, suffSum[0]); return res; # Driver code if __name__ == "__main__" : profitA = [ 2, 3, 2 ]; profitB = [ 10, 30, 40 ]; n = len(profitA); # Function to calculate max profit print(maxProfit(profitA, profitB, n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System;class GFG { // Function to calculate max profit static int maxProfit(int []profitA, int []profitB, int n) { // Prefix sum array for profitA[] int []preSum = new int[n]; preSum[0] = profitA[0]; for (int i = 1; i < n; i++) { preSum[i] = preSum[i - 1] + profitA[i]; } // Suffix sum array for profitB[] int []suffSum = new int[n]; suffSum[n - 1] = profitB[n - 1]; for (int i = n - 2; i >= 0; i--) { suffSum[i] = suffSum[i + 1] + profitB[i]; } // If all the items are sold in market A int res = preSum[n - 1]; // Find the maximum profit when the first i // items are sold in market A and the // rest of the items are sold in market // B for all possible values of i for (int i = 1; i < n - 1; i++) { res = Math.Max(res, preSum[i] + suffSum[i + 1]); } // If all the items are sold in market B res = Math.Max(res, suffSum[0]); return res; } // Driver code public static void Main(String[] args) { int []profitA = { 2, 3, 2 }; int []profitB = { 10, 30, 40 }; int n = profitA.Length; // Function to calculate max profit Console.WriteLine(maxProfit(profitA, profitB, n)); } }// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach// Function to calculate max profitfunction maxProfit(profitA, profitB, n) { // Prefix sum array for profitA[] let preSum = new Array(n); preSum[0] = profitA[0]; for (let i = 1; i < n; i++) { preSum[i] = preSum[i - 1] + profitA[i]; } // Suffix sum array for profitB[] let suffSum = new Array(n); suffSum[n - 1] = profitB[n - 1]; for (let i = n - 2; i >= 0; i--) { suffSum[i] = suffSum[i + 1] + profitB[i]; } // If all the items are sold in market A let res = preSum[n - 1]; // Find the maximum profit when the first i // items are sold in market A and the // rest of the items are sold in market // B for all possible values of i for (let i = 1; i < n - 1; i++) { res = Math.max(res, preSum[i] + suffSum[i + 1]); } // If all the items are sold in market B res = Math.max(res, suffSum[0]); return res;}// Driver codelet profitA = [2, 3, 2];let profitB = [10, 30, 40];let n = profitA.length;// Function to calculate max profitdocument.write(maxProfit(profitA, profitB, n));</script> |
Output:
80
Time Complexity: O(n)
Auxiliary Space: O(n)
Alternate Implementation:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;int maxProfit(vector<int> a, vector<int> b, int n){ // Max profit will be saved here int maxP = -1; // loop to check all possible combinations of sales for (int i = 0; i < n + 1; i++) { // the sum of the profit after the sale // for products 0 to i in market A int sumA = 0; for (int j = 0; j < min(i, (int)a.size()); j++) sumA += a[j]; // the sum of the profit after the sale // for products i to n in market B int sumB = 0; for (int j = i; j < b.size(); j++) sumB += b[j]; // Replace the value of Max Profit with a // bigger value among maxP and sumA+sumB maxP = max(maxP, sumA + sumB); } // Return the value of Max Profit return maxP;}// Driver Program11111111111111111111111int main(){ vector<int> a = { 2, 3, 2 }; vector<int> b = { 10, 30, 40 }; cout << maxProfit(a, b, 4); return 0;}// This code is contributed by pankajsharmagfg. |
Java
// Java implementation of the approachclass GFG { static int maxProfit(int[] a, int[] b, int n) { // Max profit will be saved here int maxP = -1; // loop to check all possible combinations of sales for (int i = 0; i < n + 1; i++) { // the sum of the profit after the sale // for products 0 to i in market A int sumA = 0; for (int j = 0; j < Math.min(i, a.length); j++) sumA += a[j]; // the sum of the profit after the sale // for products i to n in market B int sumB = 0; for (int j = i; j < b.length; j++) sumB += b[j]; // Replace the value of Max Profit with a // bigger value among maxP and sumA+sumB maxP = Math.max(maxP, sumA + sumB); } // Return the value of Max Profit return maxP; } // Driver Program public static void main(String args[]) { int[] a = { 2, 3, 2 }; int[] b = { 10, 30, 40 }; System.out.println(maxProfit(a, b, 4)); }}// This code is contributed by Lovely Jain |
Python3
# Python3 implementation of the approach def maxProfit (a, b, n): # Max profit will be saved here maxP = -1 # loop to check all possible combinations of sales for i in range(0, n+1): # the sum of the profit after the sale # for products 0 to i in market A sumA = sum(a[:i]) # the sum of the profit after the sale # for products i to n in market B sumB = sum(b[i:]) # Replace the value of Max Profit with a # bigger value among maxP and sumA+sumB maxP = max(maxP, sumA+sumB) # Return the value of Max Profit return maxP # Driver Program if __name__ == "__main__" : a = [2, 3, 2] b = [10, 30, 40] print(maxProfit(a, b, 4)) # This code is contributed by aman_malhotra |
C#
// Include namespace systemusing System;// C# implementation of the approachpublic class GFG{ public static int maxProfit(int[] a, int[] b, int n) { // Max profit will be saved here var maxP = -1; // loop to check all possible combinations of sales for (int i = 0; i < n + 1; i++) { // the sum of the profit after the sale // for products 0 to i in market A var sumA = 0; for (int j = 0; j < Math.Min(i,a.Length); j++) { sumA += a[j]; } // the sum of the profit after the sale // for products i to n in market B var sumB = 0; for (int j = i; j < b.Length; j++) { sumB += b[j]; } // Replace the value of Max Profit with a // bigger value among maxP and sumA+sumB maxP = Math.Max(maxP,sumA + sumB); } // Return the value of Max Profit return maxP; } // Driver Program public static void Main(String[] args) { int[] a = {2, 3, 2}; int[] b = {10, 30, 40}; Console.WriteLine(GFG.maxProfit(a, b, 4)); }}// This code is contributed by sourabhdalal0001. |
Javascript
<script>// JavaScript implementation of the approachfunction maxProfit(a, b, n){ // Max profit will be saved here let maxP = -1; // loop to check all possible combinations of sales for (let i = 0; i < n + 1; i++) { // the sum of the profit after the sale // for products 0 to i in market A let sumA = 0; for (let j = 0; j < Math.min(i, a.length); j++) sumA += a[j]; // the sum of the profit after the sale // for products i to n in market B let sumB = 0; for (let j = i; j < b.length; j++) sumB += b[j]; // Replace the value of Max Profit with a // bigger value among maxP and sumA+sumB maxP = Math.max(maxP, sumA + sumB); } // Return the value of Max Profit return maxP;}// Driver Programlet a = [ 2, 3, 2 ];let b = [ 10, 30, 40 ];document.write(maxProfit(a, b, 4));// This code is contributed by shinjanpatra</script> |
Output:
80
Time Complexity : O(N)
Auxiliary Space : O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!