#include <cassert>
#include <vector>
using namespace std;

int test(int *a, int num, int a0, int d)
{
    int i, count = 0;
    for (i = 0; i < num; i++)
    {
        if (a[i] == a0 + d * i)
            count++;
    }
    return count;
}
int howmany(int *a, int num)
{
    int max_match = 0;
    for (int i = 0; i < num; i++)
    {
        for (int j = i + 1; j < num; j++)
        {
            int d = a[j] - a[i];
            if (d % (j - i) != 0)
                continue;
            d /= j - i;
            max_match = max(max_match, test(a, num, a[i] - d * i, d));
        }
    }
    return num - max_match;
}

int main()
{
    for (int i = 0; i < 10000; i++)
    {
        int a[] = {1,4,7,11};
        assert(howmany(a, 4) == 1);
        int b[] = {-10,-5,0,5,10,15};
        assert(howmany(b, 6) == 0);
        int c[] = {157, 119, 15, -5, -25};
        assert(howmany(c, 5) == 2);
        int d[] = {1,2,4,7,11,16,22,29,37,46,56,67,79,92,106};
        assert(howmany(d, 15) == 13);
        int e[] = {1,100,10,40,2,200,-71,250,99,103,325};
        assert(howmany(e, 11) == 7);
    }
    return 0;
}

终于想到了个o(n^3)的算法,相当于穷举了.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int howmany(int *a,int num)
{
    int i,j,k,t,temp,b;
    t = num;
    for(i = 0;i < num;i++)
        for(j = i+1; j < num;j++)
        {
            if((a[j]-a[i])%(j-i)) continue;
            temp = 0;
            b = (a[j]-a[i])/(j-i);
            for(k = 0;k < num;k++)
            {
                if(a[k] != b*(k-i)+a[i]) temp++;
                if(temp >= t) break;
            }
            if(temp < t) t = temp;
            if(t == 0) return 0;
        }
    return t;
}

int p[]={1,4,7,11};

int main()
{
    printf("%d\n",howmany(p,4));
    return 0;
}

#include "stdio.h"
#include "math.h"
#include "string.h"

int tidy(int *sub, int p)
{
    int i, j, len, maxlen = 0;
    for(i = 0; i < p; i++)
    {
        len = 0;
        for(j = 0; j < p; j++)
        {
            if(sub[j] == sub[i])
                len++;
        }
        if(len > maxlen)
            maxlen = len;
    }
    return maxlen;
}
int howmany(int *a,int num)
{
    int start, step, i, m, n, len, maxlen = 0;
    int *sub = new int[num-1];

    for(start = 0; start < num-2; start++)
    {
        for(step = 1; step <= num/2; step++)
        {
            for(i = start+step, m = 0, n = 1; i < num; i += step, n++)
            {
                if((a[i]-a[start])%n)
                    continue;
                else
                    sub[m++] = (a[i]-a[start])/n;
            }
            len = tidy(sub, m)+1;
            if(len >=  ceil((float)num/2))
                return num-len;
            if(len > maxlen)
                maxlen = len;
        }
    }
    return (num-maxlen);
}
void main()
{
    int a[] = {1,100,10,40,19,200,-71,250,37,103,46};
    printf("%d", howmany(a, sizeof(a)/sizeof(int)));
}

#define EPSILON        1e-14

int howmany(int *a,int num)
{
    int        i, j, k;
    int     maxcount = 2;    // 统计最终的符合等差数列的数据个数
    int        count;            // 统计每一轮的最多的符合等差数列的数据个数
    double    dif;            // 等差
    double    temp;

    if(num <= 2)
        return 0;

    // 只要剩下的数据个数已经比最终的符合等差数列的数据个数少就不必要循环下去了
    for(i=0; i<num-2 && maxcount<num-i; ++i)
    {    // 只要剩下的数据个数已经比最终的符合等差数列的数据个数少就不必要循环下去了
        for(k=i+1; k<num-1 && maxcount<num-i; ++k)
        {// k从第i+1个数据开始，直到倒数第二个数据，让它们分别与第i个数的差作为等差
            dif   = (double)(a[k] - a[i]) / (k - i);
            temp  = a[k] + dif;
            // 统计该序列与给定数据相符的个数
            count = 2;            // 初始两个数据不用再比较了
            for(j=k+1; j<num; ++j)
            {
                if(fabs(temp-a[j]) < EPSILON)
                {
                    ++count;
                }
                temp += dif;
            }
            if(maxcount < count)
            {
                maxcount = count;
//                printf("%d: %d, %d, %d\n", i, a[i], a[k], count);
            }
        }
    }

    return num-maxcount;
}

int howmany(int *a,int num)
{
    int        i, j, k;
    int     maxcount = 2;    // 统计最终的符合等差数列的数据个数
    int        count;            // 统计每一轮的最多的符合等差数列的数据个数
    int        dif;            // 等差
    int        temp;

    if(num <= 2)
        return 0;

    // 只要剩下的数据个数已经比最终的符合等差数列的数据个数少就不必要循环下去了
    for(i=0; i<num-2 && maxcount<num-i; ++i)
    {    // 只要剩下的数据个数已经比最终的符合等差数列的数据个数少就不必要循环下去了
        for(k=i+1; k<num-1 && maxcount<num-i; ++k)
        {// k从第i+1个数据开始，直到倒数第二个数据，让它们分别与第i个数的差作为等差
            dif = (a[k] - a[i]) / (k - i);
            if(dif * (k-i) != a[k]-a[i])    // 等差必须为整数
                continue;

            temp  = a[k] + dif;
            // 统计该序列与给定数据相符的个数
            count = 2;            // 初始两个数据不用再比较了
            for(j=k+1; j<num; ++j)
            {
                if(temp == a[j])
                {
                    ++count;
                }
                temp += dif;
            }
            if(maxcount < count)
            {
                maxcount = count;
//                printf("%d: %d, %d, %d\n", i, a[i], a[k], count);
            }
        }
    }

    return num-maxcount;
}

注释掉的代码只可以处理连续情况下的数列，最后一个sample无法通过，没有改进的思路，请高手指点，谢谢，重新做了一个最复杂的。。
int howmany(int *a,int num)
{
    if(num==1)
        return -1;
    vector<int>* d=new vector<int> [num];
    vector<int>* n=new vector<int> [num];
    /*
    for(int i=1;i<num;i=i++)
    {
        int index=0;
        vector<int>::iterator pos;
        if((pos = std::find(d.begin(),d.end(),a[i]-a[i-1]))!=d.end())
        {
            index=std::distance(d.begin(),pos);
            n[index]++;
        }
        else
        {
            d.push_back(a[i]-a[i-1]);
            n.push_back(2);
        }
    }
    */
    for(int i=0;i<num;++i)
        for(int j=i+1;j<num;++j)
        {
            vector<int>::iterator pos;
            if(!((a[j]-a[i])%(j-i)))
                if((pos = std::find(d[i].begin(),d[i].end(),(a[j]-a[i])/(j-i)))!=d[i].end())
                    n[i][std::distance(d[i].begin(),pos)]++;
                else
                {
                    d[i].push_back((a[j]-a[i])/(j-i));
                    n[i].push_back(2);
                }
        }
    int max=0;
    for(int j=0;j<num;++j)
    {        
        int temp=0;
        if(!n[j].empty())
            temp=*std::max_element(n[j].begin(),n[j].end());
        if(temp>max)
            max=temp;
    }
    return num-max;
}

//注：本程序已调试通过
//编译环境，Visual C++ 6.0 + Windows XP Professional

#include <iostream.h>

int howmany(int *a, int num)
{
    int k = 0;                //用来记录所要改动数据起点的下标
    int d = a[1] - a[0];    //公差
    int n1 = 0, n2 = 0;        //用来比较

    //通过下面这个双重循环找出公差数最多的位置，用 k 记录下标
    for(int j = 1; j <= num - 1; j ++)
    {
        int dMax = a[j] - a[j - 1];
        for(int i = 1; i <= num - 1; i ++)
        {
            if(a[i] - a[i - 1] == dMax)
                n1 ++;        //在序列中公差数为dMax的个数-1
        }
        if(n1 > n2)
        {
            n2 = n1;
            k = j - 1;        //记下此时公差个数最多的第一个下标
        }
        n1 = 0;
    }

    //下面这段程序利用公差替换原来的数
    int total = 0;            //代价个数
    d = a[k + 1] - a[k];
    for(int b = k + 2; b <= num - 1; b ++)
    {
        if(a[b] != a[b - 1] + d)
        {
            a[b] = a[b - 1] + d;
            total ++;        //符合条件
        }
    }
    for(int c = k - 1; c >= 0; c --)
    {
        if(a[c] != a[c + 1] - d)
        {
            a[c] = a[c + 1] - d;
            total ++;        //符合条件
        }
    }
    return total;            //返回符合条件的代价个数
}

void main()                    //测试
{
    int b = 0;
    int a[] = {1, 5, 3, 5, 7, 8, 9, 3, 5, 12};
    cout<<"原始数据为："<<endl;
    for(int j = 0; j <= 9; j ++)
    {
        cout<<"\ta["<<j<<"]="<<a[j];
        b ++;
        if(b % 5 == 0)
            cout<<"\n";
    }
    cout<<'\n';
    b = 0;
    int n = howmany(a, 10);
    cout<<"要使这个数列成为等差数列，所花最小的代价为 "<<n<<endl;
    cout<<"改变后的数据为："<<endl;
    for(j = 0; j <= 9; j ++)
    {
        cout<<"\ta["<<j<<"]="<<a[j];
        b ++;
        if(b % 5 == 0)
            cout<<'\n';
    }
    cout<<'\n';
}
/*
程序输出结果：

原始数据:
        a[0]=1  a[1]=5  a[2]=3  a[3]=5  a[4]=7
        a[5]=8  a[6]=9  a[7]=3  a[8]=5  a[9]=12

要使这个数列成为成等数列，所花最小的代价为 7
改变后的数据为:
        a[0]=-1 a[1]=1  a[2]=3  a[3]=5  a[4]=7
        a[5]=9  a[6]=11 a[7]=13 a[8]=15 a[9]=17
*/

//注：本程序已调试通过
//编译环境，Visual C++ 6.0 + Windows XP Professional

#include <iostream.h>

int howmany(int *a, int num)
{
    int k = 0;                //用来记录所要改动数据起点的下标
    int d = a[1] - a[0];    //公差
    int n1 = 0, n2 = 0;        //用来比较

    //通过下面这个双重循环找出公差数最多的位置，用 k 记录下标
    for(int j = 1; j <= num - 1; j ++)
    {
        int dMax = a[j] - a[j - 1];
        for(int i = 1; i <= num - 1; i ++)
        {
            if(a[i] - a[i - 1] == dMax)
                n1 ++;        //在序列中公差数为dMax的个数-1
        }
        if(n1 > n2)
        {
            n2 = n1;
            k = j - 1;        //记下此时公差个数最多的第一个下标
        }
        n1 = 0;
    }

    //下面这段程序利用公差替换原来的数
    int total = 0;            //代价个数
    d = a[k + 1] - a[k];
    for(int b = k + 2; b <= num - 1; b ++)
    {
        if(a[b] != a[b - 1] + d)
        {
            a[b] = a[b - 1] + d;
            total ++;        //符合条件
        }
    }
    for(int c = k - 1; c >= 0; c --)
    {
        if(a[c] != a[c + 1] - d)
        {
            a[c] = a[c + 1] - d;
            total ++;        //符合条件
        }
    }
    return total;            //返回符合条件的代价个数
}

void main()                    //测试
{
    int b = 0;
    int a[] = {1, 5, 3, 5, 7, 8, 9, 3, 5, 12};
    cout<<"原始数据为："<<endl;
    for(int j = 0; j <= 9; j ++)
    {
        cout<<"\ta["<<j<<"]="<<a[j];
        b ++;
        if(b % 5 == 0)
            cout<<"\n";
    }
    cout<<'\n';
    b = 0;
    int n = howmany(a, 10);
    cout<<"要使这个数列成为等差数列，所花最小的代价为 "<<n<<endl;
    cout<<"改变后的数据为："<<endl;
    for(j = 0; j <= 9; j ++)
    {
        cout<<"\ta["<<j<<"]="<<a[j];
        b ++;
        if(b % 5 == 0)
            cout<<'\n';
    }
    cout<<'\n';
}
/*
程序输出结果：

原始数据:
        a[0]=1  a[1]=5  a[2]=3  a[3]=5  a[4]=7
        a[5]=8  a[6]=9  a[7]=3  a[8]=5  a[9]=12

要使这个数列成为成等数列，所花最小的代价为 7
改变后的数据为:
        a[0]=-1 a[1]=1  a[2]=3  a[3]=5  a[4]=7
        a[5]=9  a[6]=11 a[7]=13 a[8]=15 a[9]=17
*/

/*在周星星的提示下，终于你的测试数据全通过了，可是还是不知道数据多的时候会不会出错，
没了一点信心，算法巨笨，好在数组不是很大，否则运行起来又要天文时间了*/ 
#include <iostream>
#include <map>
#include <cstdlib> 
using namespace std;
int howmany(int*a,int num);
int main()
{
    int a[]={1,100,10,40,2,200,-71,250,99,103,325};
    cout<<howmany(a,11)<<endl;
    system("pause"); 
}
int howmany(int*a,int num)
{
    int i,j;
    int result=0;//它将要纪录每次循环最大可以构成等差数列的数的个数 
    map<int,int> mp;
    map<int,int>::iterator pos; 
     
    for(i=0;i<num-1;++i)
    {
       int temp;//公差 
       if(result<num-i) 
       {
       for(j=i+1;j<num;++j)
       {
       if(!((a[j]-a[i])%(j-i)))//过滤那些会出现公差为小数的情况 
         {
         temp=(a[j]-a[i])/(j-i);
         pos=mp.find(temp);/*用map为了查找时快一点，可是好像意义不大，哎！STL被我糟蹋了*/
          
         if(pos!=mp.end())
         {
             int t=++pos->second;
             if(t>result)
             result=t;
         }
         else
          mp.insert(make_pair(temp,1));
         }
         }
         mp.clear();
         }
       } 
          

    if(result==0)
    return num-2;
     
    return num-result-1;
}

我是在devC++4.9.9.2下编译运行的。