Algorithm One Day One-入力した配列のそのサブ配列の最大値を求めます
アルゴリズムはプログラミングの魂であり、プログラミング思想の精髄である--Algorithm One Day One
To be improved :
1.動的入力配列を実現する;
2.サブ配列の最大配列が存在する配列の要素をどのように見つけて出力するか.
/********************************************************************
created:2015 1 19 00:20:59
author: Jackery T(n)=Ο(n)
purpose: , ;
*********************************************************************/
#include"stdafx.h"
#include<iostream>
typedef int DataType;
DataType Arrlen(DataType array[]);
void SubAarr_MaxSum(DataType array[], DataType len);
using namespace std;
void main()
{
DataType array[]={0,12,-11,5};
DataType length=sizeof(array)/sizeof(DataType);
SubAarr_MaxSum(array,length);
}
void SubAarr_MaxSum(DataType array[], DataType len)
{
if(NULL == array || len <=0){
return;
}
int curSum = 0, SubAarr_MaxSum = 0;
// 、
for(int i=0; i<len; i++){
curSum += array[i]; //
if(curSum < 0){ // 0, 0
curSum = 0;
}
// ,
if(curSum > SubAarr_MaxSum){
SubAarr_MaxSum = curSum;
}
}
//
if(SubAarr_MaxSum == 0){
SubAarr_MaxSum = array[0];
for(int i=1; i<len; i++){
if(array[i] > SubAarr_MaxSum){
SubAarr_MaxSum = array[i];
}
}
}
cout << " :" << endl;
cout << "SubAarr_MaxSum= " << SubAarr_MaxSum<< endl;
}
To be improved :
1.動的入力配列を実現する;
2.サブ配列の最大配列が存在する配列の要素をどのように見つけて出力するか.