您可以从给定数组中找到最小的数字,并考虑该数字的所有出现。这会将数组拆分为多个子数组,现在您需要递归地解决每个子数组的问题。
在示例中:
1 2 3 1 2 3 (total = 0)
最小的数是 1:
x 2 3 x 2 3 (total = 1)
现在你有 2 个子数组。求解第一个 - 最小的数字是 2:
x 3 (total = 2)
最后你有一个元素:total = 3 求解另一个子数组使其成为 5。
以下是 C# 中的一些代码:
int Solve(int[] ar, int start, int end){
//base for the recursion -> the subarray has single element
if(end-start == 1) return 1;
//base for the recursion -> the subarray is empty
if(end-start < 1) return 0;
//find min
int m = int.MaxValue;
for(int i = start; i < end; i++)
if (ar[i] < m) m = ar[i];
int total = 1;
//find the subarrays and their contribution recursively
int subStart = start;
for(int subEnd = start; subEnd < end; subEnd++){
if(ar[subEnd] == m) {
total += Solve(ar, subStart, subEnd);
subStart = subEnd + 1;
}
}
total += Solve(ar, subStart, ar.Length);
return total;
}