动态规划思路，以及优化成O(1)的空间复杂度

遇到这种动态公式非常明显的题，直接考虑动态规划，并且列出转移方程
设置动态数组dp[i]：下标为i处之前的最大累加和(可能不包括自己也可能包括自己)以下为转移方程

• 初始化dp[0] = arr[0]
• dp[i-1] > 0 -> dp[i] = dp[i-1] + arr[i]
• dp[i-1] <= 0 -> dp[i] = arr[i]

  public int maxsumofSubarray (int[] arr) {
  // write code here
  if(arr.length == 0)return 0;
  //初始化动态数组
  int[] dp = new int[arr.length];
  dp[0] = arr[0];
  //定义最大值
  int max = dp[0];
  for(int i = 1;i < arr.length;i++){
  if(dp[i-1] > 0)
      dp[i] = dp[i-1] + arr[i];
  else
      dp[i] = arr[i];
  max = Math.max(max,dp[i]);
  }
  return max;
  }

  然后发现，这个题的动态数组其实是个累赘，因为我门只需要两个变量存储前后值则可以处理则将动态数组给优化掉

  public int maxsumofSubarray (int[] arr) {
  // write code here
  if(arr.length == 0)return 0;
  int sum = arr[0];
  int max = sum;
  for(int i = 1;i < arr.length;i++){
  sum = sum > 0 ? sum + arr[i] : arr[i];
  max = Math.max(max,sum);
  }
  return max;
  }