Chybeta

CodeTrain(3)数组单调和

题目

现定义数组单调和为所有元素i的f(i)值之和。这里的f(i)函数定义为元素i左边(不包括其自身)小于等于它的数字之和。请设计一个高效算法,计算数组的单调和。给定一个数组A同时给定数组的大小n,请返回数组的单调和。保证数组大小小于等于500,同时保证单调和不会超过int范围。

测试样例:[1,3,5,2,4,6],6
返回:27

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
class MonoSum {
public:
int calcMonoSum(vector<int> A, int n) {
int sum = 0;
int i,j;
for (j = 1;j < n;j++){
for (i = 0;i < j;i++){
sum += A[i]<=A[j]?A[i]:0;
}
}
return sum;
}
};
点击赞赏二维码,您的支持将鼓励我继续创作!
chybeta WeChat Pay

微信打赏

chybeta Alipay

支付宝打赏