//
// main.cpp
// Test
//
// Created by mac on 2017/4/24.
// Copyright © 2017年 mac. All rights reserved.
//
#include <iostream>
using namespace std;
/***********************************
解法一
最暴力解法,算出每一个子序列的和
复杂度为O(n^3)
***********************************/
int maxSubsequenceSumOne(const int arr[],const int n){
int m_iMax = 0;
int m_iTest = 0;
for(int i = 0;i<n;i++){ //i是子序列的左端位子
for(int j = i;j<n;j++){ //j是子序列的右端位子
m_iTest = 0; //m_iTest是从arr[i]到arr[j]的子列和
for(int k = i;k<=j;k++){
m_iTest += arr[k]; //求子列和
}
if( m_iTest > m_iMax ){ //如果该子列和更大
m_iMax = m_iTest; //更新最大值
}
}
}
return m_iMax;
}
/***********************************
解法二
在解法一的基础上的改进是:每计算一轮计算 i 到 j
的和,都在前一次计算的基础之上加上下一数
复杂度为O(n^2)
***********************************/
int maxSubsequenceSumTwo(const int arr[],const int n){
int m_iMax = 0;
int m_iTest = 0;
for(int i = 0;i<n;i++){ //i是子序列的左端位子
m_iTest = 0; //m_iTest是arr[i]到arr[j]的子序列和
for(int j = i;j<n;j++){ //j是子序列的右端位子
m_iTest += arr[j];
if( m_iTest > m_iMax ){ //如果该子列和更大
m_iMax = m_iTest; //更新最大值
}
}
}
return m_iMax;
}
/***********************************
解法三
分而自之
复杂度为O(NlogN)
***********************************/
int maxSubsequenceSumThree(const int arr[],const int n){
return 0;
}
/***********************************
解法四
动态读取
复杂度为O(n)
***********************************/
int maxSubsequenceSumFour(const int arr[],const int n){
int m_iMax=0;
int m_iTest=0;
for(int i = 0;i<n;i++){
m_iTest += arr[i];
if(m_iTest > m_iMax){
m_iMax = m_iTest; //发现更大值,则更新当前结果
}else if(m_iTest < 0){ //如果m_iTest小于 0 ,则将m_iTest置为0.因为一个
//负数加上后面的数只会
m_iTest = 0;
}
}
return m_iMax;
}
/********************************/
int main() {
int arr[10000] ;
int n = 0;
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout <<"One:"<< maxSubsequenceSumOne(arr,n)<<endl;
cout <<"Two:"<< maxSubsequenceSumTwo(arr,n)<<endl;
cout <<"Four:"<< maxSubsequenceSumFour(arr,n)<<endl;
return 0;
}
