C++ program for finding the maximum product of sub array of a given array

Algorithm:

1. Initialize a variable `result` and set it equal to the first element of the array, i.e., `arr[0]`.

   ```

   result = arr[0]

   ```

2. Run a loop from `i = 0` to `n-1`, where `n` is the size of the array.

   ```

   for i = 0 to n-1

   ```

3. Inside the outer loop, create a variable `mul` and set it equal to the current element `arr[i]`.

   ```

   mul = arr[i]

   ```

4. Run an inner loop from `j = i+1` to `n-1`.

   ```

   for j = i+1 to n-1

   ```

5. Inside the inner loop, update `mul` by multiplying it with the current element `arr[j]`.

   ```

   mul *= arr[j]

   ```

6. Update the `result` to be the maximum of the current `result` and `mul`.

   ```

   result = max(result, mul)

   ```

7. Outside both loops, return the final value of `result` as it contains the maximum product of a subarray.

   ```

   return result

   ```

Explanation:

- The algorithm initializes `result` with the first element of the array.

- It then iterates through each element in the array and calculates the product of subarrays starting from that element.

- The inner loop ensures that all possible subarrays starting from the current element are considered.

- At each step, the algorithm updates `result` to store the maximum product encountered so far.

- Finally, the algorithm returns the maximum product found.

Time and Space Complexity:

- Time Complexity: O(n^2) - This is due to the nested loops, where each element is considered in the outer loop, and all subsequent elements are considered in the inner loop.

- Space Complexity: O(1) - The algorithm uses a constant amount of space, regardless of the input size, as it only uses a few variables.