题解 | #数组中的逆序对#

动态规划算法

逆序对计数sum=0.
从数组大小为2开始，计算逆序对个数。
每次循环数组大小+1，对于第k次循环（数组大小为k+1），逆序对的可能情况只有2种：
1） 2个数都在前k个数中；
2） 第1个数在前k个数中，第2个数就是第k+1个数。
因为每次循环都将逆序对个数直接加到sum中，所以对于第k次循环，只需要处理第2种情况，处理算法是：遍历前k个数，如果大于第k+1个数，则sum++；

最终代码非常简单：
class Solution {
public:
int InversePairs(vector<int> data) {
unsigned int sum=0;
for(int i=1;i<data.size();i++)
{
for(int j=0;j<i;j++)
{
if(data[j]>data[i])
{
sum++;
}
}
}
return sum%1000000007;
}</int>

};

注意，sum的类型是unsigned int，因为int会出现加法溢出的情况。