输入一个 非空 整型数组,数组里的数可能为正,也可能为负。 数组中一个或连续的多个整数组成一个子数组。 求所有子数组的和的最大值。 要求时间复杂度为 O(n)。
时间: 2024-05-03 22:23:34 浏览: 17
解法:Kadane算法
Kadane算法是一种解决最大连续子数组和问题的经典算法,时间复杂度为O(n)。
算法思路:
1. 定义两个变量:maxSum和curSum,分别表示当前子数组的最大和和当前子数组的和。
2. 遍历数组,每遍历一个元素就将其加入curSum中,并更新maxSum的值。
3. 如果curSum的值小于0,那么将curSum的值设为0,因为对于后面的元素来说,包含当前元素的子数组不会是最大的。
4. 遍历结束后,maxSum的值就是最大连续子数组的和。
代码实现:
```python
def maxSubArray(nums):
maxSum = float('-inf')
curSum = 0
for num in nums:
curSum += num
maxSum = max(maxSum, curSum)
curSum = max(curSum, 0)
return maxSum
```
时间复杂度:O(n)
空间复杂度:O(1)
相关问题
python输入一个长度为n的正整数数组每个数用空格隔开
在 Python 中,可以使用 input() 函数来获取用户输入的字符串,再使用 split() 方法将字符串分割成数组。下面是一个示例代码:
```python
n = int(input("请输入数组长度:"))
arr = list(map(int, input("请输入数组,每个数之间用空格隔开:").split()))
print(arr)
```
这段程序首先使用 input() 函数询问用户输入数组长度,并将其转换为整数,再使用 input() 函数询问用户输入数组,将输入的字符串分割成数组,然后使用 map() 函数将数组中的每个元素转换为整数,最后使用 list() 函数将 map 对象转换为列表并打印出来
注意,这样写的程序在执行过程中会一次询问一个输入
java编写一个程序,输入10个整数存储到一个长度为10的整型数组中。
好的,以下是Java代码实现:
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int[] array = new int[10];
Scanner scanner = new Scanner(System.in);
System.out.println("请输入10个整数:");
for (int i = 0; i < array.length; i++) {
array[i] = scanner.nextInt();
}
System.out.println("你输入的数组为:");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
}
```
程序中定义了一个长度为10的整型数组 `array`,通过 `Scanner` 类获取用户输入。在循环中,使用 `scanner.nextInt()` 方法获取用户输入的整数,并将其存储到数组中。最后,再次遍历数组并输出每个元素的值。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)