Sponsored
In this approach, we will use a greedy strategy to partition the weights such that we achieve both the minimum and maximum possible scores for the marble distribution. The key observation here is to leverage sorting of the weights to maximize or minimize the cost of each bag.
Time Complexity: O(n log n) due to sorting the weights array.
Space Complexity: O(1) as we only use a fixed amount of extra space.
1import java.util.Arrays;
2
3class Solution {
4 public int putMarbles(int[] weights, int k) {
5 Arrays.sort(weights);
6 int total_min = 0, total_max = 0;
7 for(int i = 0; i < k; i++) {
8 total_min += weights[i] + weights[weights.length - 1 - i];
9 total_max += weights[weights.length - 1 - i] + weights[i];
10 }
11 return total_max - total_min;
12 }
13
14 public static void main(String[] args) {
15 Solution solution = new Solution();
16 int[] weights = {1, 3, 5, 1};
17 System.out.println(solution.putMarbles(weights, 2));
18 }
19}In Java, we use Arrays.sort to sort the weights and compute the scores similarly to ensure the correct partitioning.
The dynamic programming route considers evaluating partial solutions and utilizing them to form the global optimum. Here, DP arrays keep track of the best possible score up to each marble in the sequence. This methodology, while more complex, offers an exhaustive evaluation and solution-guarantee mechanism for larger constraints when direct greedy methods might struggle.
Time Complexity: O(k * n^2) where we analyze subarray splits and their costs.
Space Complexity: O(k * n) to store subproblem solutions.
1#include <vector>
#include <algorithm>
using namespace std;
int putMarbles(const vector<int>& weights, int k) {
int n = weights.size();
vector<vector<int>> dp(k, vector<int>(n, INT_MAX));
for (int j = 0; j < n; ++j) {
dp[0][j] = weights[0] + weights[j];
}
for (int i = 1; i < k; ++i) {
for (int j = i; j < n; ++j) {
for (int p = i - 1; p < j; ++p) {
dp[i][j] = min(dp[i][j], dp[i - 1][p] + weights[p + 1] + weights[j]);
}
}
}
int min_score = dp[k-1][n-1];
int max_score = 0; // Use similar logic with max function
return max_score - min_score;
}
int main() {
vector<int> weights = {1, 3, 5, 1};
cout << putMarbles(weights, 2) << endl;
return 0;
}This C++ solution designs a dynamic table to deposit cumulative cost evaluations for subarrays and achieves optimal segmentation results in both directions.