Divide an Array Into Subarrays With Minimum Cost I

Problem Description

You are given an array of integers nums of length n. The cost of an array is the value of its first element. You need to divide nums into 3 disjoint contiguous subarrays. Return the minimum possible sum of the cost of these subarrays.

Key Insights

• The cost of a subarray is determined by its first element.
• The goal is to minimize the total cost by strategically selecting the starting elements of each subarray.
• We need to handle the division into exactly three contiguous subarrays, ensuring that each subarray is non-empty.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution

To solve this problem, we can utilize a nested loop approach to iterate through the array and determine potential split points for the three subarrays. The outer loops will define the endpoints of the first two subarrays, while the remainder of the array will automatically form the third subarray. We will compute the costs associated with these partitions and keep track of the minimum sum encountered.

1. Iterate through the array to choose the end of the first subarray.
2. For each choice of the first subarray, iterate to choose the end of the second subarray.
3. The third subarray will consist of all elements following the second subarray.
4. Calculate the costs based on the first elements of each subarray and update the minimum cost accordingly.

Code Solutions