用java写一个算法：输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)

可以使用动态规划的思想来解决这个问题。定义两个变量：maxSum表示当前的最大子数组和，curSum表示当前的子数组和。

算法步骤如下：
1. 初始化maxSum和curSum为数组的第一个元素。
2. 从数组的第二个元素开始遍历，对于每个元素num：
- 如果curSum大于0，则将num加到curSum上；
- 如果curSum小于等于0，则将curSum更新为num。
3. 每次更新curSum后，比较curSum和maxSum的大小，将较大的值赋给maxSum。
4. 遍历完整个数组后，maxSum即为最大子数组的和。

以下是使用Java实现的代码：

```java
public class MaxSubarraySum {
public static int maxSubarraySum(int[] nums) {
int maxSum = nums[0];
int curSum = nums[0];

for (int i = 1; i < nums.length; i++) {
if (curSum > 0) {
curSum += nums[i];
} else {
curSum = nums[i];
}

if (curSum > maxSum) {
maxSum = curSum;
}
}

return maxSum;
}

public static void main(String[] args) {
int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int maxSum = maxSubarraySum(nums);
System.out.println("最大子数组的和为：" + maxSum);
}
}
```

以上代码的时间复杂度为O(n)，其中n为数组的长度。