貪心算法：求序列中連續(xù)的最大和的組合熄云。

想法是采取逐條記錄的方法艺糜。

循環(huán)數(shù)組中的元素，存入一個數(shù)組并使其中元素相加
幾種情況：

  ①  大于0  ---  比較當(dāng)前數(shù)組中元素和與沒有加入此元素之前的和
      （1）  大于此前的和  ---  繼續(xù)向前循環(huán)（開始序號不變）
      （2）  小于此前的和  ---  在結(jié)果集中記錄當(dāng)前狀態(tài)（開始序號赶熟，結(jié)束序號和最大值），并且
  繼續(xù)向前循環(huán)（開始序號不變）
  ②  小于0  ---  在結(jié)果集中記錄當(dāng)前狀態(tài)陷嘴，并且重新向前循環(huán)（開始序號為下一個元素）

循環(huán)完畢映砖，查找出結(jié)果集中和最多的一種結(jié)果。

使用C#實(shí)現(xiàn)的效果：

image.png

接下來是用C#實(shí)現(xiàn)的代碼:

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)
        {
            //  將數(shù)組賦值（-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;
                }
            }



            //顯示結(jié)果
            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;
            }
        }
    }
}