求数组中和最大的子数组与始末下标

2019/7/23 1:56:09 人评论 次浏览 分类:学习教程

原文链接:http://www.cnblogs.com/mingmingruyuedlut/archive/2011/12/13/2285519.html

................

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MaxSUM
{
class Program
{
static void Main(string[] args)
{
//初始化目标数组
int[] myArray = new int[] { 13, -41, 42, 26, -33, 59, 97, -90, -23, 84 };
myArray = new int[] { 1, 2, 3, -4, 5 };
//myArray = new int[] { 1, 2, 3, -4, -5 };
//myArray = new int[] { 1, 2, 3, -4, -5, 6, 7 };
//myArray = new int[] { 1, 2, 3, -4, -5, -6, 7 };
GetMaxSum(myArray, myArray.Length);
}

/// <summary>
/// 获取连续子数组的最大和
/// </summary>
/// <param name="array">目标数组</param>
/// <param name="length">数组的长度</param>
private static void GetMaxSum(int[] array, int length)
{
int sum = 0; //记录当前连续子数组的最大和
int temp = 0; //记录当前数组连续几个元素的和(当其值小于0时,重新对其赋值;【即:抛弃前面的所有元素】)
int startIndex = 0; //记录子数组(和最大)的起始位置
int endIndex = 0; //记录子数组(和最大)的终止位置
int newStartIndex = 0; //记录子数组(和最大)的新的起始位置
for (int i = 0; i < length; i++) //遍历整个目标数组
{
if (temp < 0) //如果temp < 0;则要对temp重新赋值
{
temp = array[i]; //对temp重新赋值
newStartIndex = i; //暂时记录子数组(和最大)的新的起始位置(要看后续的sum 和 temp是否发生交换)
}
else
{
temp += array[i]; //如果temp >= 0;则要继续将此时的数组元素(array[i])加入到temp中
}
if (sum < temp) //如果此时 sum < temp;则表示此时的子数组和大于之前的子数组和
{
sum = temp; //将大的子数组和temp赋值给sum
startIndex = newStartIndex; //子数组(和最大)的新的起始位置起作用了
endIndex = i; //子数组(和最大)的终止位置(只要发生交换就说明endIndex发生变化)
}
}

//显示最终的结果(从数组的第N个元素到M个元素之和最大)
DisplayResult(array, sum, startIndex, endIndex);
}

/// <summary>
/// 显示最终的结果
/// </summary>
/// <param name="array">目标数组</param>
/// <param name="maxSum">最大子数组之和</param>
/// <param name="startIndex">最大子数组的起始位置(按数组下标从0开始计数)</param>
/// <param name="endIndex">最大子数组的终止位置(按数组下标从0开始计数)</param>
private static void DisplayResult(int[] array, int maxSum, int startIndex, int endIndex)
{
Console.WriteLine("The original array is: ");
for (int i = 0; i < array.Length; i++)
{
Console.Write(array[i] + " ");
}
string expression = string.Empty;
for (int i = startIndex; i <= endIndex; i++)
{
if (array[i] < 0)
{
expression += string.Format("({0})", array[i].ToString()) + " + ";
}
else
{
expression += array[i].ToString() + " + ";
}
}
Console.WriteLine("\n");
Console.WriteLine("The final Result is : SUM({0},{1}) = {2} = {3}", startIndex, endIndex, expression.TrimEnd(new char[] { ' ', '+' }), maxSum);
}
}
}



................

转载于:https://www.cnblogs.com/mingmingruyuedlut/archive/2011/12/13/2285519.html

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->