今天难得有时间来讲讲贪心算法。

题目引入

给定一集合，找出其中最大子集。

输入：两行，第一行输入n（n<1000），代表有n个数；第二行即是n个数的集合，每个元素用空格隔开。（对于100%的数据，整形，其绝对值不超过1000）。

输出：一行，直接输出最大子集合的和max。

解题

可以使用数组。

因为对于100%的数据，其绝对值不超过1000，所以max初始值可以设置为-1001，从而保证max会被更新，是数组中的数据。

普通解法（1.0版）

很明确，先在数组中遍历子集的首位（第一层循环），再从其首位开始遍历子集的末位（第二层循环），最后用遍历前遍历得到的首位到末位累加出当前子集的和x（第三层循环），每次第三层循环结束后都更新一次max（如果x比max大， 就将x赋值给max）。

#include 
int n, a[1024], x, max=-1001;
int main(){
    scanf("%d", &n);
    for(int i=0; i
        scanf("%d", &a[i]);
    }
    for(int start=0; start
        for(int end=start; end
            x=0;
            for(int i=start; i<=end; i++){
                x+=a[i];
            }
            if(x>max){
                max=x;
            }
        }
    }
    printf("%d", max);
    return 0;
}

不走寻常路的我的解法（2.5版）

就是把上述思路的第二、三层循环合并了一下。

我们想，假如首位在a[0]，第二层循环这次遍历到a[3]，第三层循环就遍历a[0],a[1], a[2], a[3]；下次就遍历到a[4]，第三层循环：a[0], a[1], a[2], a[3],a[4]。其中第三层循环两次遍历中共同的a[0], a[1], a[2],a[3]可不可以省略呢？

当然可以。第二层循环遍历末位是从首位开始的；第三层循环亦然，且正好是到前第二层循环得到的末位结束。所以，就可以将第三层循环中的操作x+=a[i];直接放到第二层循环中（当然，重置x这一步x=0;也要外移）。

#include 
int n, a[1024], x, max=-1001;
int main(){
    scanf("%d", &n);
    for(int i=0; i
        scanf("%d", &a[i]);
    }
    for(int start=0; start
        x=0;
        for(int end=start; end
            x+=a[end];
            if(x>max){
                max=x;
            }
        }
    }
    printf("%d", max);
    return 0;
}

老师的初步优化的解法（2.0版）

最近老师老师在教我们预处理思想，这里果不其然也用上了。 思路：（别忘了， start：首位；

end：末位。（下面公式看不懂就看评论））

定义 : b n = ∑ i = 0 n a i 而 ∑ i = s t a r t e n d a i = ∑ i = 0 e n d a i − ∑ i = 0 s t a r t − 1 a i ⇒ ∑ i = s t a r t e n d a i = b e n d − b s t a r t − 1 定义: b_n = \sum_{i=0}^{n}{a_i}\\ \begin{aligned}\\ 而\sum_{i=start}^{end}{a_i} &=\sum_{i=0}^{end}{a_i} - \sum_{i=0}^{start-1}{a_i}\\ \Rightarrow \sum_{i=start}^{end}{a_i} &= b_{end} - b_{start-1}\\ \end{aligned}\\ 定义:bn​=i=0∑n​ai​而i=start∑end​ai​⇒i=start∑end​ai​​=i=0∑end​ai​−i=0∑start−1​ai​=bend​−bstart−1​​

数组b作为预处理，在输入的时候赋值。 这样我们就可以用前两层循环分别遍历首位和末位，最后直接使用预处理数组b计算出该子集。

注意，为了防止数组越界， b n b_n bn​在程序中写成 b n + 1 b_{n+1} bn+1​（相当于整体相对数组a往后移了一位），没有区别。

# include 
int a[1024], n, max=-1001, x, b[1024];
int main (){
    scanf("%d", &n);
    for (int i=0; i
        scanf("%d", &a[i]);
		b[i+1]=b[i]+a[i];
    }
	for (int start=0; start
		for (int end=start; end
			x=b[end+1]-b[start+1-1];
            if(x>max){
                max=x;
            }
		}
	}
    printf("%d", max);
    return 0;
}

使用贪心算法的解法（3.0版）

我们想，当集合中数组全为正数时，当子集合包含所有元素时最大，因为此时每个元素或多或少都对和有帮助（接地气的说）。可是，现实差强人意，会有负数的存在，负数对我们的和会起到副作用——那我们不要它就够了。我当时也是这么想，差点就自己思考出贪心算法来了，可现实差强人意——我判断当前元素是否为负数，如果是，就一同舍弃该项及以前的所有项，这显然不可行的。而贪心算法则是从集合首位开始累加，判断如果当前累加和是否小于零——如果小于零，就说明前面的连续子集都小于零，对和只有副作用，直接舍弃。

# include 
int a[1024], n, max=-1001, x;
int main (){
    scanf("%d", &n);
    for (int i=0; i
        scanf("%d", &a[i]);
    }
    for (int i=0; i
        x+=a[i];
        if (x<0){
            x=0;
        }
        if(x>max){
            max=x;
        }
    }
    printf("%d", max);
    return 0;
}

总结

我们不难发现，从1.0版本到3.0版本，思路从笨重到精炼、巧妙，代码的循环嵌套越来越少，代码运行速度也越来越快。这就是有算法支持的代码与普通的代码的差别。一名算法工程师，一天大约写100多行代码；代码不在多，在于精、在于效率、在于质量；我们要在完成之上，不断地追求完美。