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:
C++
#include <bits/stdc++.h>using namespace std;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 = std::max(max, sum); if (i == n) { return max; } for (int j = 0; j < n; j++) { sum -= arr[j]; sum += arr[i]; max = std::max(max, sum); i = (i + 1) % n; } // Return the maximum sum formed return max;}// Nikunj Sonigaraint main(){ int N = 7; int M = 3; int arr[] = { 2, 1, 3, 5, 0, 1, 4 }; // Function call long maxx = maxSum(arr, N, M); cout << maxx << endl; return 0;} |
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; }} |
Python3
def maxSum(arr, n, m): """ Function to find the maximum sum in the given time """ max_sum = 0 # Variable to store the maximum sum sum = 0 # Variable to store the current sum i = 0 while i < n and i < m: sum += arr[i] i += 1 max_sum = max(max_sum, sum) if i == n: return max_sum for j in range(n): sum -= arr[j] sum += arr[i] max_sum = max(max_sum, sum) i = (i + 1) % n # Return the maximum sum formed return max_sum# Driver codeN = 7M = 3arr = [2, 1, 3, 5, 0, 1, 4]# Function callmaxx = maxSum(arr, N, M)print(maxx) |
C#
// C# code for the above approachusing System;public class Solution { // Driver code public static void Main() { int N = 7; int M = 3; int[] arr = { 2, 1, 3, 5, 0, 1, 4 }; // Function call long maxx = maxSum(arr, N, M); Console.WriteLine(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; }}// This code is contributed by Vaibhav Nandan |
Javascript
function maxSum(arr, n, m) { // Initialize variable let max = 0; let sum = 0; let i = 0; // sum from index 0 to m-1 while (i < n && i < m) { sum += arr[i]; i++; } max = Math.max(max, sum); if (i === n) { return max; } // loop from index 0 to n for (let 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;}// Test caseconst N = 7;const M = 3;const arr = [2, 1, 3, 5, 0, 1, 4];// Function callconst maxx = maxSum(arr, N, M);console.log(maxx); |
9
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
