最大子数组问题
求哪一天买入和哪一天卖出收益更高？
1.暴力求解
遍历所有的子数组的和进行比较，求出最大值,耗费性能，很耗时间
//价格数组
int[] pricesArray = new int[] { 100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97};
//价格波动数组
int[] priceFluctuationArray = new int[pricesArray.Length];
for (int i = 1; i < pricesArray.Length; i++)
{
priceFluctuationArray[i - 1] = pricesArray[i] - pricesArray[i - 1];
}
int total = priceFluctuationArray[0];//默认数组的第一个元素是最大子数组
//开始索引和结束索引
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < priceFluctuationArray.Length; i++)
{
//取得以i为子数组起点的所有子数组
for (int j = i; j < priceFluctuationArray.Length; j++)
{
//由i，j确定一个子数组的开始和结尾
int totalTemp = 0;//临时最大子数组的和
for (int index = i; index < j+1; index++)
{
totalTemp += priceFluctuationArray[index];
}
if (total < totalTemp)
{
total = totalTemp;
startIndex = i;
endIndex = j;
}
}
}
2.分治法
分为[low,mid] 和[mid,high]
1.i,j同时位于低区间：可以继续使用递归进行解决
2.i,j同时位于高区间
3.i位于低区间，j位于该区间：取低区间中到Mid的最大主和取高区间Mid+1到High的最大值相加
//子数组的结构体
struct SubArray
{
public int startIndex;
public int endIndex;
public int total;
}
static void Main(string[] args)
{
//价格数组
int[] pricesArray = new int[] { 100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97 };
//价格波动数组
int[] priceFluctuationArray = new int[pricesArray.Length];
for (int i = 1; i < pricesArray.Length; i++)
{
priceFluctuationArray[i - 1] = pricesArray[i] - pricesArray[i - 1];
}
SubArray maxSubArrar = GetMaxSubArray(0, priceFluctuationArray.Length - 1, priceFluctuationArray);
Console.Write(maxSubArrar.startIndex + "||" + maxSubArrar.endIndex);
Console.ReadKey();
}
/// <summary>
/// 这个方法是取得array数组从low到high的最大子数组
/// </summary>
/// <param name="low"></param>
/// <param name="high"></param>
/// <param name="array"></param>
static SubArray GetMaxSubArray(int low,int high,int[] array )
{
if (low == high)
{
SubArray subArray;
subArray.startIndex = low;
subArray.endIndex = high;
subArray.total = array[low];
return subArray;
}
int mid = (low + high) / 2;//低区间是low-mid，高区间是mid+1-high
SubArray subArray1 = GetMaxSubArray(low, mid, array);
SubArray subArray2 = GetMaxSubArray(mid + 1, high, array);
//从[low，mid]中找到最大子数组
int total1 = array[mid];//最大子数组的和
int totalTemp = 0;
int startIndex = mid;
for (int i = mid; i >=low;i--)
{
totalTemp += array[i];
if (totalTemp > total1)
{
total1 = totalTemp;
startIndex = i;
}
}
//从mid+1到high之间找到最大的
int total2 = array[mid + 1];
int endindex = mid + 1;
totalTemp = 0;
for (int i = mid+1; i <= high; i++)
{
totalTemp += array[i];
if (total2 < totalTemp)
{
total2 = totalTemp;
endindex = i;
}
}
SubArray subArray3;
subArray3.endIndex = endindex;
subArray3.startIndex = startIndex;
subArray3.total = total1 + total2;
if (subArray1.total >= subArray2.total && subArray1.total >= subArray3.total)
{
return subArray1;
}else if (subArray2.total > subArray1.total && subArray2.total > subArray3.total)
{
return subArray2;
}
else
{
return subArray3;
}
}
}
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
更多精彩
