The Brute Force Approach involves iterating over all possible subarrays of the given array. For each subarray, find the maximum and minimum elements, and calculate the difference. Sum all these differences to get the final answer. While this approach is simple, it is not efficient for larger arrays due to its quadratic time complexity.
Time Complexity: O(n^2), where n is the length of the array, due to the nested loop structure.
Space Complexity: O(1), no extra data structures are used apart from loop variables.
1import java.util.*;
2
3public class SubarrayRanges {
4 public static int subArrayRanges(int[] nums) {
5 int sum = 0;
6 int n = nums.length;
7 for (int i = 0; i < n; i++) {
8 int minVal = Integer.MAX_VALUE;
9 int maxVal = Integer.MIN_VALUE;
10 for (int j = i; j < n; j++) {
11 maxVal = Math.max(maxVal, nums[j]);
12 minVal = Math.min(minVal, nums[j]);
13 sum += (maxVal - minVal);
14 }
15 }
16 return sum;
17 }
18
19 public static void main(String[] args) {
20 int[] nums = {1, 2, 3};
21 System.out.println(subArrayRanges(nums));
22 }
23}This Java implementation applies the same logic, iterating through possible subarrays using nested loops. The inner loop updates the max and min values, contributing to the total sum all subarray ranges as required.
The Monotonic Stack Approach optimizes the calculation by focusing on the contribution of each element as a maximum or minimum in various subarrays. By using two stacks, the solution efficiently determines the range extend of each number within the subarray, deriving the number of subarrays it could be the maximum or minimum of. This optimized approach emphasizes reducing redundant calculations commonly inherent in brute force methods.
Time Complexity: O(n), regarded as linear due to the stack operations limiting the number of necessary operations to a reduced count.
Space Complexity: O(n), for storing the elements in the stack structures.
1#include <iostream>
2#include <vector>
3#include <stack>
4
5using namespace std;
6
7int subArrayRanges(vector<int>& nums) {
8 long long maxSum = 0, minSum = 0;
9 vector<int> prev(nums.size()), next(nums.size());
10 stack<int> st;
11
12 for (int i = 0; i < nums.size(); ++i) {
13 while (!st.empty() && nums[st.top()] > nums[i]) {
14 next[st.top()] = i;
15 st.pop();
16 }
17 st.push(i);
18 }
19 while (!st.empty()) {
20 next[st.top()] = nums.size();
21 st.pop();
22 }
23
24 for (int i = nums.size() - 1; i >= 0; --i) {
25 while (!st.empty() && nums[st.top()] >= nums[i]) {
26 prev[st.top()] = i;
27 st.pop();
28 }
29 st.push(i);
30 }
31 while (!st.empty()) {
32 prev[st.top()] = -1;
33 st.pop();
34 }
35
36 for (int i = 0; i < nums.size(); i++) {
37 minSum += (long long)(i - prev[i]) * (next[i] - i) * nums[i];
38 }
39
40 for (int i = 0; i < nums.size(); ++i) {
41 while (!st.empty() && nums[st.top()] < nums[i]) {
42 next[st.top()] = i;
43 st.pop();
44 }
45 st.push(i);
46 }
47 while (!st.empty()) {
48 next[st.top()] = nums.size();
49 st.pop();
50 }
51
52 for (int i = nums.size() - 1; i >= 0; --i) {
53 while (!st.empty() && nums[st.top()] <= nums[i]) {
54 prev[st.top()] = i;
55 st.pop();
56 }
57 st.push(i);
58 }
59 while (!st.empty()) {
60 prev[st.top()] = -1;
61 st.pop();
62 }
63
64 for (int i = 0; i < nums.size(); i++) {
65 maxSum += (long long)(i - prev[i]) * (next[i] - i) * nums[i];
66 }
67
68 return (int)(maxSum - minSum);
69}
70
71int main() {
72 vector<int> nums = {1, 2, 3};
73 cout << subArrayRanges(nums) << endl;
74 return 0;
75}The C++ implementation demonstrates stack usage to handle each number's potential influence over multiple subarrays achieved by alternatingly focusing it as minimum and maximum practitioners along the array iterations.