1.暴力解法
找出每个子数组比较大小，如果当前子数组的和比当前所求最大值大就更新，会超时，时间复杂度：O（n2），需要两次循环，空间复杂度：O（1）；
import java.util.*;

public class Solution {
/*
* max sum of the subarray
* @param arr int整型一维数组 the array
* @return int整型
*/
public int maxsumofSubarray (int[] arr) {
// write code here
if(arr.length==0)//数组为空
return 0;
int res=0;
for(int i=0;i<arr.length;i++){
int max=0;
for(int j=i;j<arr.length;j++){
max+=arr[j];
if(max>res)
res=max;
}
}
return res;
}
}
2.贪心
对数组进行一次遍历，用一个临时的数组存当前结果，贪心的思想，就是能要肯定会要的，如果累加和比当前结果大的话，就会要，如果当前累加和，为负数，肯定是不能要的，应当把当前累加和置为0，时间复杂度：O（n），循环一次；空间复杂度：O（1）
import java.util.;

public class Solution {
/*
* max sum of the subarray
* @param arr int整型一维数组 the array
* @return int整型
*/
public int maxsumofSubarray (int[] arr) {
// write code here
if(arr.length==0)
return 0;
int res=0;
int temp=0;//存放临时结果
for(int i=0;i<arr.length;i++){
temp+=arr[i];
if(temp>res)
res=temp;
if(temp<0)
temp=0;
}
return res;
}
}
3.动态规划
可以利用典型的dp数组，边界条件为dp[0]=arr[0],res=arr[0];递推公式为dp[i]=Math.max(dp[i-1]+arr[i],arr[i]),res=Math.max(dp[i],res);其实整体的思路也是贪心，如果当前的累加和比当前值小的话，显然前面那些数是没有意义，可以舍去。其实可以将dp数组换成一个变量temp，减少空间的使用，时间复杂度为：O（n），循环了一次；空间复杂度为：O（1）
import java.util.;

public class Solution {
/*
* max sum of the subarray
* @param arr int整型一维数组 the array
* @return int整型
*/
public int maxsumofSubarray (int[] arr) {
// write code here
if(arr.length==0)
return 0;
int res=0;
int temp=0;//存放临时结果
for(int i=0;i<arr.length;i++){
temp=temp+arr[i]>arr[i]?temp+arr[i]:arr[i];
res=Math.max(temp,res);
}
return res;
}
}
4.分治（二分法）
将数组分成二部分，最大累加和可能在左边，可能在右边，可以包含两边，计算包含两边的，左边，右边，三者中的最大值即为最大累加和，再跟时间复杂度：O（nlogn），递归和遍历一次数组，空间复杂度：O（logn）；递归深度。
import java.util.;

public class Solution {
/**
* max sum of the subarray
* @param arr int整型一维数组 the array
* @return int整型
*/
public int mergeMax(int []arr,int left,int mid,int right){
int sum1=0;
int leftMax=0;
for(int i=mid;i>=0;i--){//计算左边最大累加和
sum1+=arr[i];
leftMax=Math.max(leftMax,sum1);
}
int sum2=0;
int rightMax=0;
for(int i=mid+1;i<=right;i++){//计算右边最大累加和
sum2+=arr[i];
rightMax=Math.max(rightMax,sum2);
}
return leftMax+rightMax;//返回左右最大累加和之和
}
public int searchMax(int []arr,int left,int right){
if(left==right)
return arr[left];
int mid=(left+right)/2;
int leftMax=searchMax(arr,left,mid);//左边累加和
int rightMax=searchMax(arr,mid+1,right);//右边累加和
int mergeMax=mergeMax(arr,left,mid,right);//包含两边累加和
return Math.max(Math.max(leftMax,rightMax),mergeMax);
}
public int maxsumofSubarray (int[] arr) {
// write code here
if(arr.length==0)
return 0;
return searchMax(arr,0,arr.length-1);
}
}