算法：贪心算法

贪心算法：求序列中连续的最大和的组合。

想法是采取逐条记录的方法。

循环数组中的元素，存入一个数组并使其中元素相加
几种情况：

  ①  大于0  ---  比较当前数组中元素和与没有加入此元素之前的和
      （1）  大于此前的和  ---  继续向前循环（开始序号不变）
      （2）  小于此前的和  ---  在结果集中记录当前状态（开始序号，结束序号和最大值），并且
  继续向前循环（开始序号不变）
  ②  小于0  ---  在结果集中记录当前状态，并且重新向前循环（开始序号为下一个元素）

循环完毕，查找出结果集中和最多的一种结果。

使用C#实现的效果：

image.png

接下来是用C#实现的代码:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace test
{
    class Program
    {
        const int COUNT = 10;

        const int MIDDLE = 0;
        static void Main(string[] args)
        {
            //  将数组赋值（-100 -- 100）
            int[] iArray = new int[COUNT];
            Random random = new Random(DateTime.Now.Millisecond);
            for (var i = 0; i < COUNT;i++ )
            {
                iArray[i] = random.Next(-COUNT, COUNT);
            }

            //  下面是算法
            List<Caculation> cache = new List<Caculation>();
            var data = new Caculation();
            int add = 0;

            for (int i = 0; i < COUNT ; i++)
            {
                add += iArray[i];

                if (add > 0)
                {
                    if (add >= data.max)
                    {
                        data.end = i;
                        data.max = add;
                        if (i == COUNT - 1)
                        {
                            cache.Add(data);
                        }
                    }
                    else
                    {
                        cache.Add(data);    //  提交上一个
                        var temp = new Caculation(data);
                        temp.end = i;       //  下一个不归零
                        temp.max = add;
                        data = temp;
                    }
                }
                else
                {
                    data.max = add;
                    data.end = i;
                    cache.Add(data);        //  提交这一个
                    add = 0;                //  下一个归零
                    var temp = new Caculation();
                    temp.start = i + 1;
                    data = new Caculation(temp);
                }
            }
            

            int max = 0;
            Caculation c = null;
            for (var i = 0; i < cache.Count; i++)
            {
                Console.WriteLine(cache[i].ToString());
                if (cache[i].max > max)
                {
                    c = cache[i];
                    max = c.max;
                }
            }



            //显示结果
            int s = 0;
            foreach (var i in iArray)
            {
                Console.Write(i+" , ");
                s += i;
            }
            Console.WriteLine("\nThe Max is" + c);

            Console.ReadLine();
        }
        class Caculation
        {
            public int max;
            public int start, end;
            public Caculation()
            {
                this.max = 0;
                this.start = 0;
                this.end = 0;
            }
            public Caculation(Caculation c)
            {
                this.max = c.max;
                this.start = c.start;
                this.end = c.end;
            }
            public override string ToString()
            {
                return "This Caculation is Max: " + max + " Start: " + start + " end: " + end;
            }
        }
    }
}