Maximum Sum Alternating Subarray

0 0 5 minutes read

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 1^stloop and the sum starting from odd indices, in the 2^nd 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 array
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 = 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 code
int 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 approach
 
import 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 array
def 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 array
arr = [-4, -10, 3, 5]
n = len(arr)
 
# return sum
ans = alternatingSum(arr, n)
print(ans)
 
# This code is contributed by Parth Manchanda

C#

// C# implementation for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the maximum alternating
// sum of a subarray for the given array
static 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 code
public 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:

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 zambiatek!