有一个无序的一维数组，里面有正有负 求子数组的和里面最大的那个和

这个问题可以使用动态规划来解决，时间复杂度为 O(n)。

定义两个变量：max_sum 和 cur_sum。max_sum 保存目前为止找到的最大子数组和，cur_sum 保存当前正在处理的子数组的和。

从数组的第一个元素开始，遍历数组。对于每个元素，将它加到 cur_sum 中。如果 cur_sum 变成了负数，说明当前的子数组不可能成为最大子数组的前缀，因此将 cur_sum 重置为0，从下一个元素开始重新计算子数组和。

每次计算出新的 cur_sum 后，将它和 max_sum 进行比较，如果 cur_sum 大于 max_sum，则更新 max_sum。

最后，返回 max_sum 即可。

下面是一个示例代码：

int maxSubArraySum(int arr[], int n) 
{ 
    int max_sum = arr[0]; 
    int cur_sum = 0; 
  
    for (int i = 0; i < n; i++) 
    { 
        cur_sum += arr[i]; 
  
        if (cur_sum > max_sum) 
            max_sum = cur_sum; 
  
        if (cur_sum < 0) 
            cur_sum = 0; 
    } 
  
    return max_sum; 
} 

相关问题

C如何实现查找一个无序的字符数组中有没有对应的元素

C语言中可以使用线性查找（顺序查找）算法来查找一个无序的字符数组中是否存在某个元素。其基本思路是从数组的第一个元素开始逐个比对，直到找到目标元素或者遍历完整个数组。

以下是一个简单的示例代码：

#include <stdio.h>
#include <stdbool.h>

bool linearSearch(char arr[], int size, char target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return true;
        }
    }
    return false;
}

int main() {
    char arr[] = {'a', 'b', 'c', 'd', 'e'};
    int size = sizeof(arr) / sizeof(char);
    char target = 'c';
    if (linearSearch(arr, size, target)) {
        printf("%c exists in the array.\n", target);
    } else {
        printf("%c does not exist in the array.\n", target);
    }
    return 0;
}

上述代码中，`linearSearch` 函数接收一个字符数组、数组大小和目标字符作为参数，返回一个布尔值表示目标字符是否存在于数组中。`main` 函数中定义了一个字符数组 `arr`，数组大小为 `size`，目标字符为 `target`。程序运行后，会输出 `c exists in the array.`，表示目标字符 `c` 存在于数组中。

用JAVA编写方法，传入一个整形无序数组， 将数组变为有序数组

可以使用Java内置的排序方法来实现对无序数组的排序。以下是一个示例方法：

import java.util.Arrays;

public class ArraySorter {
    public static void sortArray(int[] arr) {
        Arrays.sort(arr);
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 7, 1, 3};
        System.out.println("Before sorting: " + Arrays.toString(arr));

        sortArray(arr);

        System.out.println("After sorting: " + Arrays.toString(arr));
    }
}

使用`Arrays.sort()`方法可以对整型数组进行排序。在示例中，我们先输出排序前的数组，然后调用`sortArray()`方法对数组进行排序，最后输出排序后的数组。运行上述代码，输出结果如下：

Before sorting: [5, 2, 7, 1, 3]
After sorting: [1, 2, 3, 5, 7]

这样就将无序数组变为有序数组了。请注意，此方法会直接修改原始数组，如果你不想改变原始数组，可以先创建一个副本进行排序。