算法初步 基本概念 最大子数组和
算法是研究时空复杂度的，时空复杂度使用大O表示。
时间：基本操作次数（汇编指令条数，比如算法执行完需要n行指令，则时间复杂度为O(n)，时间复杂度是忽略前面的系数的，算法执行需要2n行指令，时间复杂度也是O(n)，所以不用考虑一行指令对应多条汇编，系数是忽略的。O(n^2 + n)可以认为是o(n^2)，因为n的平方远大于n） 空间：占用内存字节数
优秀的算法：O(1) < O(logn) < O(n^1/2) < O(n) < O(nlogn) 需要优化的算法：O(n^2) < O(n^3) < O(2^n) < O(n!)
案例 最大子数组求和 leetcode 53题 给定数组a[1…n]，求最大子数组和，即找出1<=i<=j<=n，使a[i]+a[i+1]+…+a[j]最大。
方法一：暴力枚举，时间复杂度为o(n^3)，无法通过leetcode，显示超时。 时间复杂度为o(n^3)，空间复杂度o(1)
class Solution {
public int maxSubArray(int[] nums) {
int sum = 0;
int msum = Integer.MIN_VALUE;
for(int i=0;i<nums.length;i++){
for(int j=i;j<nums.length;j++){
for(int k=i;k<=j;k++){
sum+=nums[k];
}
if(msum<sum){
msum = sum;
}
sum = 0;
}
}
return msum;
}
}方法二：优化枚举，时间复杂度为o(n^2)，空间复杂度为o(n)（很多部分都重复加了，要去除冗余，直接通过了leetcode，很神奇，执行时间为66ms,超过了百分之4的人。
class Solution {
public int maxSubArray(int[] nums) {
int sum = 0;
int msum = Integer.MIN_VALUE;
int[] s = new int[nums.length + 1];
s[0] = 0;
for(int i=0;i<nums.length;i++){
s[i + 1] = s[i] + nums[i];
}
for(int i=0;i<nums.length;i++){
for(int j=i;j<nums.length;j++){
sum = s[j+1] - s[i];
if(msum<sum) msum = sum;
}
}
return msum;
}
}方法三：假设s[i] 为nums[0] 到nums[i]的和，那么要想求出最大子数组和，就需要得到max(s[j] - s[i])，将s[j]固定，则需要求min(s[i])，所以此问题由最大子数组和转换成了求最小和（最小s[i]）的问题，这次提交执行时间为10ms，超过了47.22%的人 （经验：求和变求差 求积变求和 求指数变对数 求最大变求最小），时间复杂度为O(n)，空间复杂度为O(n)。
class Solution {
public int maxSubArray(int[] nums) {
int msum = Integer.MIN_VALUE;
int si = 0;
int sj = 0;
int minsi = 0;
for(int j = 0; j<nums.length;j++){
sj += nums[j];
if(si < minsi){ //min[0,6] = min(min[0,5] [6]) 求最小和可以通过增量来实现，si的（0,6）的最小和其实就是（0,5）的si最小和和si[6]最比较，这种增量方式的转换技巧很实用
minsi = si;
}
if(sj - minsi > msum){
msum = sj - minsi;
}
si += nums[j];
}
return msum;
}
}方法四：将以上代码稍微调整一下就是贪心算法了 时间8ms，超过89.81%。贪心算法的思路比较难以理解，后面介绍贪心算法的时候再回过头来看看。
class Solution {
public int maxSubArray(int[] nums) {
int msum = Integer.MIN_VALUE;
int sum = 0;
for(int j = 0; j<nums.length;j++){
sum += nums[j];
if(sum>msum) msum = sum;
if(sum < 0) sum = 0;
}
return msum;
}
}