Maximizing Subarray sum with constrained traversal and addition time

By Ann Roberts On May 9, 2023

Given two integers N and M representing the Length of arr[] and number of seconds. The task is to maximize the sum of the subarray where it takes 0.5secs to travel in consecutive elements and 0.5secs to add a value of the element in sum. It is given that one can start from any element.

Example:

Input: N = 7, M = 3, arr[] = { 2, 1, 3, 5, 0, 1, 4 }
Output: 9
Explanation: One can start from index 1 and move to index 2 and then to index 3. Hence, the total sum is = 1 + 3 + 5 = 9.

Input: N = 6, M = 2, arr[] = { 1, 6, 2, 5, 3, 4 }
Output: 8
Explanation: One can start from index 1 and move to index 2. In this case, One will gather 6 + 2 = 8 sum. One can also start from index 3 and move to index 4. In this case, too, One will gather 5 + 3 = 8 sum.

Approach: This can be solved with the following idea:

The approach used in the above code is to find the maximum sum subarray of size M in the given array by sliding a window of size M over the array and keeping track of the maximum sum seen so far.

Below are the steps involved in the implementation of the code:

Initialize max and sum to 0.
Traverse the array from index 0 to m-1 and add up the values to sum.
Compare max with sum and store the larger value in max.
If i (the current index) is equal to n, exit and return max.
Loop through the remaining indices from m to n-1 and do the following:
- Subtract arr[j] (the value at index j) from the sum.
- Add arr[i] (the value at index i) to the sum.
- Compare max with sum and store the larger value in max.
- Increment i using the modulo operator % to simulate a circular array.
Return max.

Below is the code implementation of the above approach:

Java

// Java code for the above approach:
import java.util.*;

public class Solution {

    // Driver code
    public static void main(String[] args)
    {
        int N = 7;
        int M = 3;
        int[] arr = { 2, 1, 3, 5, 0, 1, 4 };

        // Function call
        long maxx = maxSum(arr, N, M);
        System.out.println(maxx);
    }

    // Function to find maximum sum
    // in given time
    public static long maxSum(int[] arr, int n, int m)
    {
        long max = 0;
        long sum = 0;

        int i = 0;
        while (i < n && i < m) {
            sum += arr[i];
            i++;
        }

        max = Math.max(max, sum);
        if (i == n) {
            return max;
        }

        for (int j = 0; j < n; j++) {
            sum -= arr[j];
            sum += arr[i];

            max = Math.max(max, sum);

            i = (i + 1) % n;
        }

        // Return the maximum sum formed
        return max;
    }
}

Time Complexity: O(N)
Auxiliary Space: O(1)

Last Updated :
08 May, 2023

Like Article

Save Article