Given an array arr[] of size N, the task is to find the maximum alternating sum of a subarray possible for a given array.
Alternating Subarray Sum: Considering a subarray {arr[i], arr[j]}, alternating sum of the subarray is arr[i] – arr[i + 1] + arr[i + 2] – …….. (+ / -) arr[j].
Examples:
Input: arr[] = {-4, -10, 3, 5}
Output: 9
Explanation: Subarray {arr[0], arr[2]} = {-4, -10, 3}. Therefore, the sum of this subarray is 9.Input: arr[] = {-1, 2, -1, 4, 7}
Output: 7
Approach: The given problem can be solved by using Dynamic Programming. Follow the steps below to solve the problem:
- Initialize a variable, say sum as 0, which will hold a maximum alternating subarray sum and a variable, say sumSoFar, to store the sum of subarrays starting from even indices in the 1st loop and the sum starting from odd indices, in the 2nd loop.
- In every iteration of both the loops, update sum as max(sum, sumSoFar).
- Finally, return the maximum alternating sum stored in the sum variable.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum alternating// sum of a subarray for the given arrayint alternatingSum(int arr[],int n){ int sum = 0; int sumSoFar = 0; // Traverse the array for (int i = 0; i < n; i++) { // Store sum of subarrays // starting at even indices if (i % 2 == 1) { sumSoFar -= arr[i]; } else { sumSoFar = max( sumSoFar + arr[i], arr[i]); } // Update sum sum = max(sum, sumSoFar); } sumSoFar = 0; // Traverse the array for (int i = 1; i < n; i++) { // Store sum of subarrays // starting at odd indices if (i % 2 == 0) { sumSoFar -= arr[i]; } else { sumSoFar = max( sumSoFar + arr[i], arr[i]); } // Update sum sum = max(sum, sumSoFar); } return sum;}// Driver codeint main() { // Given Input int arr[] ={ -4, -10, 3, 5 }; int n = sizeof(arr)/sizeof(arr[0]); // Function call int ans = alternatingSum(arr,n); cout<<ans<<endl; return 0;}// This code is contributed by Potta Lokesh |
Java
// Java implementation for the above approachimport java.io.*;class GFG { // Function to find the maximum alternating // sum of a subarray for the given array public static int alternatingSum(int[] arr) { int sum = 0; int sumSoFar = 0; // Traverse the array for (int i = 0; i < arr.length; i++) { // Store sum of subarrays // starting at even indices if (i % 2 == 1) { sumSoFar -= arr[i]; } else { sumSoFar = Math.max( sumSoFar + arr[i], arr[i]); } // Update sum sum = Math.max(sum, sumSoFar); } sumSoFar = 0; // Traverse the array for (int i = 1; i < arr.length; i++) { // Store sum of subarrays // starting at odd indices if (i % 2 == 0) { sumSoFar -= arr[i]; } else { sumSoFar = Math.max( sumSoFar + arr[i], arr[i]); } // Update sum sum = Math.max(sum, sumSoFar); } return sum; } // Driver code public static void main(String[] args) { // Given Input int arr[] = new int[] { -4, -10, 3, 5 }; // Function call int ans = alternatingSum(arr); System.out.println(ans); }} |
Python3
# Python implementation for the above approach# Function to find the maximum alternating# sum of a subarray for the given arraydef alternatingSum(arr, n): sum_ = 0 sumSoFar = 0 # Traverse the array for i in range(n): # Store sum of subarrays # starting at even indices if i % 2 == 1: sumSoFar -= arr[i] else: sumSoFar = max(arr[i], sumSoFar + arr[i]) # Update sum sum_ = max(sum_, sumSoFar) sumSoFar = 0 # Traverse array for i in range(1, n): # Store sum of subarrays # starting at odd indices if i % 2 == 0: sumSoFar -= arr[i] else: sumSoFar = max(arr[i], sumSoFar + arr[i]) sum_ = max(sum_, sumSoFar) # update sum return sum_# given arrayarr = [-4, -10, 3, 5]n = len(arr)# return sumans = alternatingSum(arr, n)print(ans)# This code is contributed by Parth Manchanda |
C#
// C# implementation for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the maximum alternating// sum of a subarray for the given arraystatic int alternatingSum(int []arr,int n){ int sum = 0; int sumSoFar = 0; // Traverse the array for(int i = 0; i < n; i++) { // Store sum of subarrays // starting at even indices if (i % 2 == 1) { sumSoFar -= arr[i]; } else { sumSoFar = Math.Max( sumSoFar + arr[i], arr[i]); } // Update sum sum = Math.Max(sum, sumSoFar); } sumSoFar = 0; // Traverse the array for(int i = 1; i < n; i++) { // Store sum of subarrays // starting at odd indices if (i % 2 == 0) { sumSoFar -= arr[i]; } else { sumSoFar = Math.Max( sumSoFar + arr[i], arr[i]); } // Update sum sum = Math.Max(sum, sumSoFar); } return sum;}// Driver codepublic static void Main(){ // Given Input int []arr = { -4, -10, 3, 5 }; int n = arr.Length; // Function call int ans = alternatingSum(arr,n); Console.Write(ans);}}// This code is contributed by SURENDRA_GANGWAR |
Javascript
<script>// JavaScript implementation for the above approach // Function to find the maximum alternating // sum of a subarray for the given array function alternatingSum(arr) { var sum = 0; var sumSoFar = 0; // Traverse the array for (var i = 0; i < arr.length; i++) { // Store sum of subarrays // starting at even indices if (i % 2 == 1) { sumSoFar -= arr[i]; } else { sumSoFar = Math.max( sumSoFar + arr[i], arr[i]); } // Update sum sum = Math.max(sum, sumSoFar); } sumSoFar = 0; // Traverse the array for (var i = 1; i < arr.length; i++) { // Store sum of subarrays // starting at odd indices if (i % 2 == 0) { sumSoFar -= arr[i]; } else { sumSoFar = Math.max( sumSoFar + arr[i], arr[i]); } // Update sum sum = Math.max(sum, sumSoFar); } return sum; } // Driver code // Given Input var arr = new Array ( -4, -10, 3, 5 ); // Function call var ans = alternatingSum(arr); document.write(ans); // This code is contributed by shivanisinghss2110</script> |
Output:
9
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!
… [Trackback]
[…] There you can find 84140 additional Info to that Topic: geeksforgeeks.org/maximum-sum-alternating-subarray/ […]