/*
 * 求连续的子数组的和为最大数组及其和
 * 要求：
 * 1.只求子数组，不包含子数组为全集的情况
 * 2.本算法考虑了数组和一直递减趋势的情况
 * 3.本算法考虑了数组和一直递增趋势的情况
 * C# auto indent Ctrl+A -> Ctrl+K -> Ctrl+F
 * 
 * 
 * */
using System;
using System.Collections.Generic;
using System.Text;

namespace Design_Pattern.Observer
{
    public class MaxArray
    {
        private static int maxsum;
        public static void Main(String[] args)
        {
            int[] array = { 1, -2, 3, 10, -4, 7, 2, -5 };
            //int[] array = { 1, -9, -10};
            //int[] array = { 1, 0, 2 };
            int[] m = new int[array.Length];
            m[0] = array[0];
            List<int> maxsubarray = new List<int>();
            MaxArray.findMaxSubArray(array, m, ref maxsubarray);

            Console.Write("max sub array:");
            // 这里考虑m[0]时最大值的情况，即这个数组整体趋势递减
            if (maxsum == m[0])
            {
                Console.Write(m[0]);
            }
            else
            {
                // 这里的maxsubarray不包含m[0]也可以为递增作贡献的情况 所以当数组为{ 1, 0, 2 }结果不正确
                // 可加上这层处理
                foreach (int item in maxsubarray)
                {
                    Console.Write(item + " ");
                }
            }
            
            Console.ReadLine();
        }
        public static void findMaxSubArray(int[] array, int[] m, ref List<int> maxsubarray)
        {
            // 包含子数组为全集 注意边界 不是array.Length-1
            int n = array.Length;
            m[0] = array[0];
            for (int i = 1; i < n; i++)
            {
                if (m[i - 1] < 0)
                {
                    m[i] = array[i];
                }
                else
                {
                    m[i] = m[i - 1] + array[i];
                    maxsubarray.Add(array[i]);
                }

            }

            Console.WriteLine("the max sum for sub array:");
            Console.WriteLine(MaxArray.GetArrayMax(m));

            Console.WriteLine("new sum array m:");
            foreach (int item in m)
            {
                Console.Write(item + " ");

            }
            Console.WriteLine();
        }

        public static int GetArrayMax(int[] array)
        {
            int max = array[0];
            foreach (int  item in array)
            {
                if (item > max)
                {
                    max = item;
                }
            }
            maxsum = max;
            return max;
        }
    }
}